import sys input = lambda: sys.stdin.readline().rstrip() # sys.setrecursionlimit(10**7) # sys.set_int_max_str_digits(10**6) # import pypyjit # pypyjit.set_param('max_unroll_recursion=-1') def mp():return map(int,input().split()) def lmp():return list(map(int,input().split())) def lm1(LIST): return list(map(lambda x:x-1, LIST)) def mps(A):return [tuple(map(int, input().split())) for _ in range(A)] def stoi(LIST):return list(map(int,LIST)) def itos(LIST):return list(map(str,LIST)) def atoi(LIST): return [ord(i)-ord("a") for i in LIST] def Atoi(LIST): return [ord(i)-ord("A") for i in LIST] def LT(LIST,N): return LIST[bisect.bisect_left(LIST,N)-1] def LE(LIST,N): return LIST[bisect.bisect_right(LIST,N)-1] def GT(LIST,N): return LIST[bisect.bisect_right(LIST,N)] def GE(LIST,N): return LIST[bisect.bisect_left(LIST,N)] def LTidx(LIST,N): return bisect.bisect_left(LIST,N)-1 def LEidx(LIST,N): return bisect.bisect_right(LIST,N)-1 def GTidx(LIST,N): return bisect.bisect_right(LIST,N) def GEidx(LIST,N): return bisect.bisect_left(LIST,N) def bitA(X,A):return X & 1<= s: print(a[-1]) exit() ok = a[-1] ng = 0 while (ok-ng) != 1: mid = (ok+ng)//2 if check(mid):ok = mid else:ng = mid print(ok)