The Big Prize timer 1s memory 1024MB

커다란 상품은 유명한 TV 게임 쇼이다.

당신은 다행히도 결승전까지 진출했다.

당신 앞에는 n개의 상자가 한 줄로 놓여져 있는데, 왼쪽부터 차례로 0부터 n-1까지 번호가 매겨져 있다.

각각의 상자에는 상자를 열 때까지는 볼 수 없는 상품 하나가 들어 있다.

상은 서로 다른 v ≥ 2 종류가 있다.

이 종류는 가치의 내림차순으로 1부터 v까지 번호가 매겨져 있다.

1번 종류 상품은 가장 비싼 것으로 다이아몬드이다.

다이아몬드가 들어있는 상자는 정확히 하나이다.

v번 종류 상품은 가장 싼 것으로 사탕이다.

게임을 더 재미있게 하기 위해서, 싼 종류의 상품의 수는 이보다 비싼 종류의 상품 수보다 훨씬 많다.

보다 구체적으로, 2 ≤ t ≤ v인 t에 대해서 다음 조건이 성립한다:

만약 t-1종류의 상품이 k개 있다면, t종류 상품은 k²개보다 많이 있다.

당신의 목적은 다이아몬드를 얻는 것이다.

게임이 모두 끝날 때 당신은 상자 하나를 열어야 하고, 이 상자에 들어있는 상품을 받는다.

열 상자를 정하기 전에, 당신은 게임의 사회자인 Rambod에게 질문들을 할 수 있다.

각각의 질문으로, 당신은 어떤 상자 i를 지정한다.

Rambod는 질문에 대한 답으로, 두 정수가 저장된 배열 a를 준다.

이것의 의미는 다음과 같다:

- 상자 i의 왼쪽에 있는 상자들 중에서 정확히 a₀개의 상자에는 상자 i에 들어있는 상품보다 비싼 상품이 들어 있다.

- 상자 i의 오른쪽에 있는 상자들 중에서 정확히 a₁개의 상자에는 상자 i에 들어있는 상품보다 비싼 상품이 들어 있다.

예를 들어, n = 8이라고 하자.

질문으로, 당신이 i = 2번 상자를 지정했다.

이에 대한 답으로 Rambod는 a= [1, 2]라고 대답했다.

이 답의 의미는 다음과 같다.

- 0번 상자와 1번 상자 중 정확히 하나에 2번 상자에 들어있는 상품보다 비싼 상품이 들어있다.

- 3, 4, ... 7번 상자 중 정확히 둘에 2번 상자에 들어있는 상품보다 비싼 상품이 들어있다.

당신의 임무는 적은 수의 질문을 통해서 다이아몬드가 있는 상자를 찾는 것이다.

당신은 다음 함수를 구현해야 한다.

int find_best(int n)

이 함수는 그레이더에 의해 단 한번 호출된다.

- n : 상자의 수.

- 이 함수의 리턴값은 다이아몬드가 들어있는 상자의 번호이다. 즉, 리턴값이 정수 (0 ≤ d ≤ n-1) 라면 상자 d에 1번 종류 상품이 들어있다.

위 함수는 다음 함수를 호출할 수 있다.

vector<int> ask(int i)

- i : 당신이 질문하는 상자의 번호. i 값은 0 이상 n-1 이하이다.

- 이 함수의 리턴값은 원소가 2개인 배열 a이다. a₀은 상자 왼쪽에 있는 상자들에 들어있는 더 비싼 상품의 수이며, a₁은 상자 오른쪽에 있는 상자들에 들어있는 더 비싼 상품의 수이다.​

1 <= n <= 100 000

ask 함수를 5000회 이내로 사용하여 정답을 찾을 시 100점을 받을 수 있다.