arr = [0,1,2,3,4,5,6,7,8,8,9]
lower, upper = 0, len(arr)
while lower != upper:
mid = (lower + upper) // 2
if arr[mid] >= mid:
lower = mid
else:
upper = mid - 1
print(arr[lower])
YXJyID0gWzAsMSwyLDMsNCw1LDYsNyw4LDgsOV0KCmxvd2VyLCB1cHBlciA9IDAsIGxlbihhcnIpCndoaWxlIGxvd2VyICE9IHVwcGVyOgogICAgbWlkID0gKGxvd2VyICsgdXBwZXIpIC8vIDIKICAgIGlmIGFyclttaWRdID49IG1pZDoKICAgICAgIGxvd2VyID0gbWlkCiAgICBlbHNlOgogICAgICAgdXBwZXIgPSBtaWQgLSAxCgpwcmludChhcnJbbG93ZXJdKQ==