# def solution(num):
# num = list(map(str,num))
# print(num)
# s = []
# for i in range(len(num)):
# s.append(num[i] * 2)
# print(s)
# # num.sort(reverse=True)
# num.sort(key=lambda x: x*12345, reverse=True)
# return str(int(''.join(num)))
#
# a = [3, 30, 34, 5, 9]
#
# # a = [11100, 10110, 10111, 10001, 110100]
# print(solution(a))
# def solution(arr):
# ans = []
# ans.append(arr[0])
# for i in range(1,len(arr)):
# if ans[-1] != arr[i]:
# ans.append(arr[i])
# return ans
#
# a = [1,1,3,3,0,1,1]
# print(solution(a))
# pp = []
# cnt = 0
# def search(x,c):
# global pp
# global cnt
# if x+1<len(pp) and pp[x+1] >=100:
# pp[x+1] = -1
# search(x+1,c+1)
# else:
# cnt = c
# return
# def solution(pro, spe):
# global pp
# global cnt
# ans = []
# ll = len(pro)
# pp = pro
# while pro[-1] != -1:
# for i in range(ll):
# if pp[i] != -1:
# pp[i] += spe[i]
#
#
# for i in range(ll):
# cnt = 0
# if pp[i] >= 100 and (i==0 or pp[i-1]==-1):
# pp[i] = -1
# search(i,1)
# ans.append(cnt)
# print(pp)
# return ans
#
# a = [95, 90, 99, 99, 80, 99]
# b = [1, 1, 1, 1, 1, 1]
# print(solution(a,b))
# def solution(s):
# answer = True
# cnt = 0
# ll = len(s)
# for i in range(ll):
# if s[i] == '(':
# cnt += 1
# elif s[i] == ')':
# cnt -= 1
# if cnt < 0:
# answer = False
# break
# if cnt != 0:
# answer = False
# return answer
#
# a = ")()("
# print(solution(a))
# def solution(pri, loc):
# answer = 0
# key = []
# ll = len(pri)
# for i in range(ll):
# u = [i, pri[i]]
# key.append(u)
# ma = 0
# for i in range(ll):
# if ma < pri[i]:
# ma = pri[i]
# cnt = 0
# while len(key) != 0:
# #print('max', ma)
# #print('v', ll, key)
# flag = 0
# for i in range(ll):
# if ma == key[i][1]:
# flag = 1
# break
# if flag == 1:
# if key[0][1] == ma:
# cnt += 1
# ll -= 1
# c = key.pop(0)
# if c[0] == loc:
# answer = cnt
# #print(cnt)
# #print(key, ma)
# else:
# temp = key.pop(0)
# key.append(temp)
# flag = 0
# for i in range(ll):
# if key[i][1] == ma:
# flag = 1
# break
# if flag == 0:
# # print('v')
# ma -= 1
# else:
# ma -= 1
# return answer
#
# a = [2, 1, 3, 2]
# b = 2
# print(solution(a,b))
# def solution(b_l, wei, t_w):
# cnt = 0
# bri = [0]*b_l
# arr = []
# while len(t_w) > 0:
# cnt += 1
# arr.append(bri[-1])
# for i in range(b_l):
# temp = bri[i]
# bri[i] = bri[i+1]
# bri[i+1] = temp
# if sum(bri) + t_w[0] > wei:
# bri[0] = 0
# else:
# bri[0] = t_w[0]
# return cnt
#
# a = 2
# b = 10
# c = [7,4,5,6]
# print(solution(a,b,c))
# def solution(pri):
# answer = []
# for i in range(len(pri)):
# key = pri[i]
# cnt = 0
# for j in range(i, len(pri)):
# if pri[j] < key:
# cnt += 0
# else :
# cnt += 1
# answer.append(cnt-1)
#
# return answer
#
# a = [5, 6, 4, 3, 2, 1]
# print(solution(a))