Pseudo-dichotomic search P60373

Consider a hidden vector V with n integer numbers in strictly increasing order. Given an integer x that belongs to V, you will play a game to guess the position j where V[j] = x. You have to use a “black box” B, with parameters x and a position i inside V. If there is a j ∈ {i − 1, i, i + 1 } such that V[j] = x, you win the game. Otherwise, B will tell you whether x < V[i−1] or x > V[i+1].

Given n, what is the minimum number of calls to B to win the game?

Input

Input consists of several cases, each one with an n between 1 and 10¹⁸.

Output

For every n, print the worst-case number of calls to B to win the game, assuming a strategy that minimizes that worst-case cost.