코딩테스트 한 번에 작성한것들,,

#컴프리헨션 샘플 (comprehension)

# word = [sorted(list(inp[i])) for i in range(n)]

# find = [len(inp[i]) if len(inp[i]) >= len(word[0]) else len(word[0]) for i in range(n)

#---1912연속합 런타임에러

 

# import math

# inp = int(input())

# numbers=input()

# number = numbers.split(' ')

# number = list(map(int,number))

# #윗줄 완성  정수형 리스트

# pos=0

# summ=0

# result =1

# b=max(number)

# for i in range(int(math.factorial(inp)/inp)):

#     for j in range(pos,len(number)):

#         summ+=number[j]

#         b=max(summ,b)

#     pos+=1

#     summ=0

# print(b)

#----7785 회사에 남은 사람 딕셔너리 사용해보기

#런타임에러 -> 성공

# n=int(input())

 

# result ={}

# a=[]

# for i in range(n):

#     name,state = input().split()

 

#     if name in result :

#         del result[name]

#     else:

#         result[name]=state

# for i in result :

#     a.append(i)

# a.sort(reverse=True)

# for i in a:

#     print(i)

#---1110 더하기사이클

# inp = int(input())

# cnt=0

# if inp <10:

#     a=0

#     b=inp

#     c=a+b

# a=inp//10

# b=inp%10

# c=a+b

# original = str(a)+str(b)+str(c)

# for i in range(1000):

#     a=b

#     b=c%10

#     c=a+b

#     cnt+=1

#     compare = str(a)+str(b)+str(c)

#     if original == compare:

#         break

 

#     c=c%10

#

# print(cnt)

# ---백준 1026 보물

 

# answer =0

# inp = int(input())

# inp_a=input()

# inp_b=input()

# a=inp_a.split()

# b=inp_b.split()

# for i in range(inp):

#     a[i]=int(a[i])

#     b[i]=int(b[i])

# a.sort()

# b.sort(reverse=True)

# for i in range(inp):

#     answer +=a[i]*b[i]

 

# print(answer)

# #--백준 1835 카드(실패->성공)

# n = int(input())

# l = [n]

 

# for i in range(n-1,0,-1):

#     l = [i]+l

#     for j in range(i):

#         l = l[n-i:] + l[0:n-i]

# for i in range(n):

#     print(l[i],end=' ')

 

#  1) 2 1 4 3에서 2를 가장 뒤로 옮긴다. (1 4 3 2)

#  2) 1을 책상 위에 옮겨놓는다. (4 3 2)

#  3) 4 3 2 에서 4, 3을 뒤로 옮긴다. (2 4 3)

#  4) 2를 책상 위로 옮겨놓는다. (4 3)

#  5) 4 3 에서 가장 앞에 있는 것을 뒤로 3번 옮긴다. (3 4)

#  6) 3을 책상 위로 옮겨놓는다. (4)

#  7) 4를 책상 위로 옮겨놓는다. (완료)

#--백준 2777 숫자놀이 (실패)

# N = int(input())

# go = True

# answer=[]  #입력받는 값에 대한 정답을 저장

# quo=[]  #나누어주는 수들을 저장해주는 몫(quotient) 배열

# for i in range(N):

#     inp=int(input())

#     for j in range(2,9):  # 한 자릿수를 봐야하기때문에 나누는 수가 10이 넘어가면 안됨

#         if inp%j==0:

#             while inp%j==0:    #j가 2이면 2로 나눌 수 없을 때까지 진행

#                 inp/=j

#                 tmp = str(j)    # 정수형으로 받아서 바로 append를 시켜주면 에러가 남

#                 quo.append(tmp)   # 배열의 각각의 원소들의 특징때문이라고 하는데 이건 나중에 자세히.

 

#     if inp>=10:     #10미만의 수로 나누어도 inp이 10을 넘으면 -1이 답

#         answer.append(-1)

#     elif len(quo)==0:  #inp이 1인경우

#         answer.append(1)   

#     else:

#         for k in range(50):  #대충 잡은 숫자(입력조건 만족)

#             for s in range(int(len(quo)/2)):   

#                 if k==len(quo)-1:  #두개씩 봐주기때문에 인덱스 주의

#                     go = False  #이중포문 나가기 작업

#                     break

#                 else:

#                     if int(quo[k])*int(quo[k+1])<10:  # (작은숫자가 입력이면 계속 에러가 났는데 인덱스 문제였음)

#                         quo[k+1]=int(quo[k])*int(quo[k+1])

#                         #앞,뒤 숫자를 곱하고 이것이 10미만이면 뒤에다가 이 수를 저장.

#                         quo[k+1]=str(quo[k+1])

#                         #문자열 처리

#                         del quo[k]

#                         # 앞 숫자 삭제

#                     # elif len(quo)>1:

#                     #     pass  

#             if go == False: 

#                 break 

           

#         answer.append(len(quo))

#     # print(quo)

#     quo=[]              

 

# for i in range(len(answer)):

#     print(answer[i])

#--백준 2193 이친수  (피보나치)

# N = int(input())

# a=[1,1]

# cnt=0

# if N<3:

#     print(1)

# else:

#     while (cnt!=N-2):

#         a.append(sum(a))

#         a=a[1:]

#         cnt+=1

 

#     print(a[1])

#--백준 1543 문서검색 (문제 잘못 이해한거)

#문장안에 똑같은거 몇개 반복되는지 푸는 알고리즘

#abcabcab

# a=[]

# a=input()

# find=[]

# find=input()

# cnt=0

# for i in range(len(a)):

#     cnt2=cnt

#     cnt=0

#     for j in range(i,len(a)):

#         temp=a[i:j]

#         print(i,j,temp)

#         if temp in a:

#             cnt+=1

#     realcnt=max(cnt,cnt2)    

 

# print(realcnt)      

 

# ---백준1543문서검색

# a=[]

# a=input()

# find=[]

# find=input()

# cnt=0

 

# for i in range(len(a)):

#     for j in range(i,len(a)):

#         if a[0:len(find)]==find:

#             a=a[len(find):]

#             cnt+=1

#         else:

#             a=a[1:]

        

# print(cnt)

#---파이썬 2777 숫자놀이 (성공)

# N=int(input())

 

# for i in range(N):

#     cnt=0

#     inp = int(input())

#     if inp ==1:

#         print(inp)

#     else:

#         for j in range(9,1,-1):

#             while inp %j==0:

#                 inp=inp/j

#                 cnt+=1

#         if inp >=10:

#             print(-1)

#         else:

#             print(cnt)

#---백준 2015 수들의 합 4 (시간초과)

# from itertools import combinations

# from itertools import permutations

# #combinations,permutations의 차이

# N,number = map(int,input().split())

# a=map(int,input().split())

# cnt=0

# a=list(a)

# for i in range(1,N):

#     for c in permutations(a,i):  #combi튜플로 저장돼서 바로 처리해주기

#         if sum(c)==number:

#             cnt+=1

 

# print(cnt)

#---백준 12919 A와 B 2 (런타임에러)

# s=input()  #A

# t=input()  #BABA

# arr=[]

# arr.append(t)

# go = False

# if len(t)<2:

#     go = True

# else:

#     while(len(arr)>1):

#         print(arr)

#         if arr[0]==s:

#             go = True

#             break

 

#         tmpa = arr[0]

#         tmpb = arr[0]

#         tmpb = tmpb[::-1]

        

#         if tmpa[-1]=="A":

#             arr.append(tmpa[0:-1])

#         if tmpb[-1]=="B":

#             arr.append(tmpb[0:-1])

#         arr=arr[1:]

 

# if go ==True:

#     print(1)

# else : print(0)    

#---백준 1434 책 정리

# x,k = map(int,input().split())

# box = list(map(int,input().split()))

# book = list(map(int,input().split()))

 

# ind_x=0

# ind_k=0

# while(1):

#     if box[ind_x]>=book[ind_k]:

#         box[ind_x]-=book[ind_k]

#         ind_k+=1

#         if ind_k ==k:

#             break

#     elif box[ind_x]<book[ind_k]:

#         ind_x+=1

#         if ind_x==x:

#             break

#     else: break

 

# # print(box)

# print(sum(box))

#--_백준 1002 터렛

# import math

 

# N = int(input())

# for i in range(N):

#     x1,y1,r1,x2,y2,r2 = map(int,input().split())

#     distance =math.sqrt(pow(x2-x1,2)+pow(y2-y1,2))

#     if distance ==0 and r1==r2:

#         print(-1)

#     elif distance>r1+r2 or abs(r1-r2)>distance:

#         print(0)

#     elif distance == r1+r2 or abs(r1-r2)==distance:  

#         #연산할때 좌항우항 바뀌면 틀리나봄!

#         print(1)

#     else:

#         print(2)

#---백준 14255 부분수열의 합 (실패)

# from itertools import combinations

# N=int(input())  #3

# inp=list(map(int,input().split()))   #5,1,2

# j=0

# arr=[] #부분합 저장

# if len(inp)==1:

#     print(inp[0])

# else:

#     for i in range(1,N+1):

#         for c in combinations(inp,i):

#             arr.append(sum(c))

#     arr.sort()

#     arr = list(set(list(arr)))

#     temp=1

#     for j in range(len(arr)):

#         if(temp!=arr[j]):

#             print(temp)

#             break

#         else:

#             temp+=1

            

# if len(arr)==j+1:

#     print(temp)

#---- 백준 3989 유행성 독감 (시간초과)

# import time

# k,m,n = map(int, input().split())  # 첫째날에 걸린 n명을 이용, m으로 나눈 나머지는 다음날, k 일째

# oned = list(map(int,input().split()))  #첫째날에 걸린사람 번호

# start = time.time()

# l=[oned]

# l.append(oned[:])

# l.append(oned[:])

 

# for _ in range(k-1):

#     for i in range(len(l[0])):

#         for j in range(len(l[1])):

#             tmp = l[0][i]*l[1][j] % m

#             if tmp not in l[2]:

#                 l[2].append(tmp)

#     l[1]=l[2]

#     l[2]=[]

 

# l[1].sort()

 

# for i in range(len(l[1])):

#     print(l[1][i],end=' ')

# print()

# print(time.time()-start)

#--- 백준 1697 숨바꼭질 (실패)

# s,t = map(int,input().split())  #5, 17

# arr=[(0,t)]

# check =[]

# cnt=0

# if s>t :

#     print(t-s)

# elif s==t:

#     print(0)

# else:

#     while(1):

#         if (arr[0][1]-1==s or arr[0][1]+1==s ): #or arr[0][1]//2==s

#             print(cnt)

#             break 

#         if check[(arr[0][1])]!=1 and arr[0][1]-1>=0:

#             arr.append(cnt,arr[0][1]-1)

#         if check[(arr[0][1])]!=1 and arr[0][1]+1>=0:

#             arr.append(cnt,arr[0][1]+1)

#         if check[(arr[0][1])]!=1 and arr[0][1]!=0 and arr[0][1]%2==0 and arr[0][1]//2>0:

#             arr.append(cnt,arr[0][1]//2)

 

#         check[arr[0][1]]=1

 

#         del arr[0]

 

#         if cnt-1 ==l[0][0]:

#             continue

#         else:

#             cnt+=1

        

# ---- 백준 2667 단지번호붙이기(살퍄)

# N = int(input())

# arr=[]

# for _ in range(N):

#     inp = list(map(int,input().split()))

#     arr.append(inp)

# print(arr)

 

# dan = [[0]]

# cnt=0

 

# for i in range(N):

#     for j in range(N):

#         arr[i][j]

# ----백준 6603 로또

# from itertools import combinations

 

# while(1):

#     inp = list(map(int,input().split()))

#     number = inp[0]

#     if number==0:

#         break

#     inp= inp[1:]

#     arr=inp[:]

#     tmp = list(combinations(arr,6))

 

#     for i in range(len(tmp)):

#         for j in range(6):

#             print(tmp[i][j], end=' ')

#         print()

#     print()

# ----- 백준 2605 줄 세우기

# n=int(input())   # 5

# number = []      # 0 1 1 3 2

# number=list((map(int,input().split())))

# number=number[1:]

# arr=[]

# arr.append(1)

# cnt=2

# for i in number:

#     if i==0:

#         arr.append(cnt)

#     else:

#         tmp = i*(-1)

#         arr.insert(tmp,cnt)

#     cnt+=1

 

# for i in range(n):

#     print(arr[i],end=' ')

    

# ---- 백준 2607 비슷한 단어 (실패)

# 글자 구성이 같고 순서만 다른경우

# 글자 구성이 같지만 한글자만 틀린 경우(+1 or -1)

# N=int(input())

# word=[]

# for i in range(N):

#     tmp = input()

#     tmp=sorted(tmp)

#     word.append(tmp)

# # word[0] = DOG

# main = word[0]

# print(word)

# cnt=0

# for i in range(1,N):

#     # i 비교대상 인덱스 (word)

#     dif = abs(len(word[i])-len(main))

#     if dif >=2 : 

#         pass

#     elif dif <=1 :

#         inter = set(set(main).intersection(set(word[i])))

#         main = set(main)

#         if inter == main or inter == set(word[i]):

#             print(inter,i)

#             cnt+=1

 

# print(cnt)

# ---- 백준 2607 비슷한 단어 (실패)

# 글자 구성이 같고 순서만 다른경우

# 글자 구성이 같지만 한글자만 틀린 경우(+1 or -1)

# N=int(input())

# word=[]

# for i in range(N):

#     tmp = input()

#     if i>=1 and abs(len(tmp)-len(word[0])) >=2 : 

#         pass

#     tmp=sorted(tmp)

#     word.append(tmp)

# # word[0] = DOG

# main = word[0]

# print(word)

# cnt=0

# for i in range(1,N):

#     # i 비교대상 인덱스 (word)

#     length = len(main)

#     if abs(len(word[i])-length) >=2 : 

#         continue

#     elif abs(len(word[i])-length)<=1 :

#         inter = set(set(main).intersection(set(word[i])))

#         main = set(main)

#         if inter == main or inter == set(word[i]):

#             print(inter,i)

#             cnt+=1

 

# print(cnt)

# ----백준 2606 바이러스 (성공)

# 아이디어 :

# 1. 입력받는 숫자 쌍을 x,y라고 한다면 입력을 받다가 x와y중에 1이 있다면

# 미리 만든 리스트 0번째에다가 저장한다. 다음 반복문에서 x,y만 있는 리스트를

# 돌아보면서 0번째 리스트에 하나라도 있다면 0번째에 저장하고 아니면 1번째에 저장

# 마지막에 set처리 해줘서 중복제거

# 2. 입력받는 숫자 쌍을 x,y라고 한다면 입력을 받다가 x와y중에 1이 있다면

# check라는 리스트를 만들어서 해당 인덱스를 1로 바꾸고

# 또 다음 반복문에서 check가 1인 인덱스와 같이 입력받은 것들이 있다면 그 값을

# 1로 해주고 아닌것들은 다른 수들로 저장해서 나중에 1인 것들만 따로 세기 

#

# computer = int(input())

# ssang = int(input())

# arr=[]

# check =[[],[]]   # 1번한테 바이러스 걸린 컴퓨터는 [0]에 저장, 나머지는 [1]

# for i in range(ssang):

#     tmp = list(map(int,input().split()))

#     if 1 in tmp:

#         check[0].append(tmp[0])

#         check[0].append(tmp[1])

#         check[0]=list(set(check[0]))

#     arr.append(tmp)

 

# for i in range(len(arr)):

#     for j in arr[i]:

#         if j in check[0]:

#             check[0].append(arr[i][1])

#         else:

#             check[1].append(arr[i][0])

#             check[1].append(arr[i][1])

 

# cnt=0

# check[0]=list(set(check[0]))

# while(cnt<len(arr)):

#     for x,y in arr:

#         if x in check[0]:

#             check[0].append(y)

#         elif y in check[0]:

#             check[0].append(x)

#     check[0]=list(set(check[0]))    

#     cnt+=1

 

# print(len(check[0])-1)

# -----백준 2607 비슷한 단어 (실패)

# N=int(input())

# word = input()

# for i in range(N):

#     inp=input()

#     inp = sorted(inp)

#     word.append(inp)

 

# print(word)

# cnt=0

# main=word[0]

# for i in range(1,N+1):

#     length = abs(len(main)-word[i])

#     if length ==0 and main == word[i]:

#         cnt+=1

#     elif length ==1:

# # set(main).intersection(set(word[i]))

    

     

# ---- 백준 2608 로마숫자

# rom ={"M":1000,"CM":900,"D":500,"CD":400,"C":100,"XC":90,"L":50,"XL":40}

# cnt=0

# result =0

# while(cnt<2):

#     inp=input()

#     for i in range(len(inp)):

#         for j in range(i+1,len(inp)):

#             if inp[i:j]=="CM":

#                 result += 900

#                 inp=inp[0:i]+inp[j:]

#             elif inp[i:j]=="CD":

#                 result+=400

#                 inp=inp[0:i]+inp[j:]

#             elif inp[i:j]=="XC":

#                 result+=90

#                 inp=inp[0:i]+inp[j:]

#             elif inp[i:j]=="XL":

#                 result+=40

#                 inp=inp[0:i]+inp[j:]

    

#     for i in inp:

#         if i=="I":

#             result+=1

#         elif i=="V":

#             result+=5

#         elif i=="X":

#             result+=10

#         elif i=="L":

#             result+=50

#         elif i=="C":

#             result+=100

#         elif i=="D":

#             result+=500

#         elif i=="M":

#             result+=1000

 

#     cnt+=1

#     print(inp)

#     print(result)   

#------ 백준 2798 블랙잭 (성공)

# from itertools import combinations

# number, limit = input().split()

# number=int(number)

# limit=int(limit)

# numbers=[]

# numbers=list((map(int,input().split())))

# maxx=numbers[0]

# tmp = list(combinations(numbers,3))

# cnt=0

# for c in range(len(tmp)):

#     if sum(tmp[c])<=limit:

#         maxx=max(sum(tmp[c]),maxx)

#     cnt+=1

# print(maxx)

#---- 백준 2587 대표값2 (성공)

# arr=[]

# for i in range(5):

#     arr.append(int(input()))

# arr.sort()

# print(int(sum(arr)/5))

# print(arr[2])

#---- 백준 2591 숫자카드 (실패)

# from itertools import combinations

# from itertools import permutations

# inp = input()

# number=[int(inp[i]) for i in range(len(inp))]

# print(number)

# # tmp=list

# print(list(permutations(number,2)))

#----백준 2588 곱셈 (성공)

# one = int(input())

# two = input()

# three = one*int(two[2])

# four = one*int(two[1])

# five = one*int(two[0])

# six = three+four*10+five*100

# print(three,four,five,six,sep='\n')

#---- 백준 2590 색종이 (무한 루프)

# paper=[]

# cnt=0

# for i in range(1,6):

#     tmp = int(input())

#     for j in range(tmp):

#         paper.append(i)   # 1 1 1 1 1 2 2 2 4 5

# paper.sort(reverse=True)

# while(0 in set(paper) or len(paper)>=1):

#     tmpcnt=0

#     tmpcnt2=0

#     if paper[0]==6:

#         cnt+=1

#     elif paper[0]==5:

#         while(tmpcnt<11 and 1 in paper):

#             paper.remove(1)

#             tmpcnt+=1

#         tmpcnt=0

#         cnt+=1

#         paper[1:]

#     elif paper[0]==4:

#         while(tmpcnt<5 and 2 in paper):

#             paper.remove(2)

#             tmpcnt+=1

#         while(tmpcnt2<(5-tmpcnt)*4 and 1 in paper):

#             paper.remove(1)

#             tmpcnt2+=1

#         cnt+=1

#         paper[1:]

#     elif paper[0]==3:

#         pass

# print(cnt)

        

#--- 백준 10797 10부제 (성공)

# N = int(input())

# numbers=list(map(int,input().split()))

# cnt=0

# for i in numbers:

#     if i == N:

#         cnt+=1

# print(cnt)

#---- 백준 2420 사파리월드 (성공)

# a,b=map(int,input().split())

# print(max(a,b)-min(a,b))

        

#---- 백준 2475 검증수 (성공)

# number=list(map(int,input().split()))

# sum=0

# for i in number:

#     sum+=i*i

# print(sum%10)

#---- 백준 2386 도비의 영어 공부 (성공)

# result =[]

# while(1):

#     cnt=0

#     inp=input()

#     if inp =="#":

#         break

#     for i in inp:

#         if i ==inp[0] or i==inp[0].upper():

#             cnt+=1

#     result.append([inp[0],cnt-1])

 

# for i in result:

#     print(i[0],i[1])

#----백준 1259 팰린드롬수 (성공)

# result=[]

# while(1):

#     inp=input()

#     if inp == "0":

#         break

#     inp=list(inp)

#     length = int(len(inp)/2)

 

#     if len(inp)%2==0:

#         front = inp[0:length]

#         back = inp[length:]

#     else:

#         front = inp[0:length]

#         back = inp[length+1:]  

              

#     if front == back[::-1]:

#         result.append("yes")

#     else:

#         result.append("no")

 

# for i in result:

#     print(i)

#---- 백준 1264 모음의 개수

# # 'a', 'e', 'i', 'o', 'u'

# alp = ["a","e","i","o","u"]

# while(1):

#     cnt=0

#     inp=input()

#     if inp =="#":

#         break

#     for i in inp:

#         if i in alp or i.lower() in alp:

#             cnt+=1

#     print(cnt)

#---- 백준 1547 공 (성공)

# N=int(input())

# ball = []

# now=1

# for i in range(N):

#     inp= list((map(int,input().split())))

#     inp.sort()

#     ball.append(inp)

# for i in ball:

#     if i[0] ==now:

#         now=i[1]

#     elif i[1]==now:

#         now=i[0]

# print(now)

#---- 백준 1731 추론 (성공)

# N = int(input())

# numbers=[]

# for i in range(N):

#     numbers.append(int(input()))

 

# if numbers[1]-numbers[0] == numbers[2]-numbers[1]:

#     print(numbers[N-1]+numbers[1]-numbers[0])

# elif numbers[1]/numbers[0] == numbers[2]/numbers[1]:

#     print(int((numbers[N-1]*numbers[1]/numbers[0])))

# ----- 백준 10101 삼각형외우기 (성공)

# tri = []

# for _ in range(3):

#     tri.append(int(input()))

# if sum(tri)==180:

#     if tri[0]==60 and tri[1]==60 and tri[2]==60:

#         print("Equilateral")

#     elif tri[0]==tri[1] or tri[0]==tri[2] or tri[1]==tri[2]:

#         print("Isosceles")

#     else:

#         print("Scalene")

# else:

#     print("Error")

    

# ----- 백준 16171 나는 친구가 적다 (실패)

# mix = input()

# word=[]

# find=input()

# for i in range(len(mix)):

#     if mix[i].isalpha()!=1:

#         mix=mix.replace(mix[i]," ")

# mix=list(mix)

# while(" " in mix):

#     mix.remove(" ")

# mix=''.join(mix)

# print(mix)

# if find in mix:

#     print(1)

# else:

#     print(0)

# ----- 백준 1213 팰린드롬 만들기 (메모리초과)

# from itertools import permutations

# inp = input()

# length= int(len(inp)/2)

# front=[]

# back=[]

# result=[]

# permu = list(permutations(inp,len(inp)))

# co=(list(set(list(permu))))

# for c in co:

#     if len(inp) %2==0:

#         front= c[0:length]

#         back = c[length:]

#         if front==back[::-1] and c not in result:

#             result.append(c) 

#     else:

#         break   

# for c in co:

#     if len(inp)%2!=0:

#         front = c[0:length]

#         back = c[length+1:]

#         if front==back[::-1] and c not in result:

#             result.append(c)

#     else:

#         break

# result.sort()

# if len(result)>0:

#     print("".join(result[0]))

# else:

#     print("I'm Sorry Hansoo")

#-----백준 1181 단어정렬 (성공)

# N=int(input())

# word=[]

# check=[]

# for i in range(N):

#     inp=input()

#     if inp in check:

#         pass

#     else:

#         word.append([len(inp)])    

#         word[-1].append(inp)

#         check.append(inp)

 

# word.sort()

# for i in range(len(word)):

#     print(word[i][1])

#----- 백준 1920 수 찾기 (시간초과)

# inp=int(input())

# N=list(input().split())

# inp=int(input())

# M=list(input().split())

# result=[]

# for i in range(len(M)):

#     if M[i] in N:

#         result.append("1")

#     else:

#         result.append("0")

# print(" ".join(result))

#-----백준 10828 스택

# n=int(input())

# stack =[]

# for i in range(n):

#     tmp=input()

#     if tmp == 'top' or tmp == 'size' or tmp == 'size' or tmp == 'pop' or tmp == 'empty' :

#         continue

#     else:

#         oper,num=tmp.split()

 

#     if oper=='push':

#         stack.append(num)

#     elif oper=='pop':

#         if len(stack)<1:

#             print(-1)

#         else:

#             stack.pop()

#             print(stack[-1])

#     elif oper=='empty':

#         if len(stack)>0:

#             print(0)

#         else:

#             print(1)

#     elif oper=='top':

#         if len(stack)>0:

#             print(stack[-1])

#         else:

#             print(-1)

#     else:

#         print(len(stack))

#----- 백준 10828 스택 (시간초과)

# n=int(input())

# stack=[]

# for i in range(n):

#     inp = input()

#     if inp[0:2]=="pu":

#         oper,num=inp.split()

#         stack.append(num)

#     else:

#         if inp=="pop":

#             if len(stack)==1:

#                 stack.pop

#                 print(0)

#             elif len(stack)>1:

#                 stack.pop()

#                 print(stack[-1])

#             else:

#                 print(-1)

#         elif inp=="size":

#             print(len(stack))

#         elif inp=="empty":

#             if stack !=[]:

#                 print(0)

#             else:

#                 print(1)

#         elif inp=="top":

#             if stack!=[]:

#                 print(stack[-1])

#             else:

#                 print(-1)

      

# cnt=0    #[[cnt,몫]]

# n=int(input())

# que=[[cnt,n]]

# check=[]

# aa=n

# while(que[0][1]!=1):

#     aa=que[0][1]

#     check.append(aa)

#     if que[0][1]==1:

#         break

#     elif aa not in check:

#         if aa%3==0:

#             que.append([cnt,aa//3])

#         if aa%2==0:

#             que.append([cnt,aa//2])

#         que.append([cnt,aa-1])

#         que=que[1:]

#     cnt+=1        

#     print(que)

# print(que[0][0]-1)

# 2822 점수계산 (성공)

# score=[]

# index=[]

# for i in range(8):

#     tmp = int(input())

#     score.append(tmp)

# sort_list=score[:]

# sort_list.sort(reverse=True)

# for i in range(5):

#     index.append(score.index(sort_list[i])+1)

# index.sort()

# print(sum(sort_list[0:5]))

# for i in index:

#     print(i,end=' ')

# 알고리즘 2차과제 파이썬으로

def binsearch(n,low,high,inp):

    mid = int((low+high)/2)

    print("l : {}, h : {}".format(low,high))

    if(low>high):

        return -1

 

    if(n[mid]==inp):

        return mid

    elif (n[mid]>inp):

        return binsearch(n,low,mid-1,inp)

    else:

        return binsearch(n,mid+1,high,inp)

 

n = [1,2,3,4,5,6,7,8,9,10]

print(binsearch(n,0,10,1))