#include "prize.h"
#include <bits/stdc++.h>
#define Loop(x,l,r) for (ll x = (l); x < (ll)(r); ++x)
#define LoopR(x,l,r) for (ll x = (r)-1; x >= (ll)(l); --x)
typedef long long ll;
typedef std::pair<int, int> pii;
typedef std::pair<ll , ll > pll;
using namespace std;
const int N = 200'010;
jmp_buf ret_env;
int ret_val;
auto ret_ask(int i, int x = 1)
{
static int asked[N] = {};
assert(asked[i] == 0);
asked[i] += x;
auto v = ask(i);
if (v[0] + v[1] == 0) {
ret_val = i;
longjmp(ret_env, 1);
}
return v;
}
int cnt_expen = 0;
void solve(int l, int r, int cntl, int cnt, int cntr)
{
if (cnt == 0 || l >= r)
return;
int ml = (l+r)/2, mr = (l+r)/2;
vector<int> lst;
int lstd;
while (l < ml || mr < r) {
if (mr < r) {
lstd = 1;
lst = ret_ask(mr++);
if (lst[0] + lst[1] == cnt_expen)
break;
}
if (l < ml) {
lstd = 0;
lst = ret_ask(--ml);
if (lst[0] + lst[1] == cnt_expen)
break;
}
}
if (l == ml && r == mr)
return;
int to_l = lstd == 1? mr-ml-1: 0;
int to_r = lstd == 0? mr-ml-1: 0;
solve(l, ml, cntl, lst[0] - cntl - to_l, lst[1] + to_l);
solve(mr, r, lst[0] + to_r, lst[1] - cntr - to_r, cntr);
}
int find_best(int n)
{
mt19937_64 rd(time(0) + (ll)(void *)find_best);
if (setjmp(ret_env))
return ret_val;
if (n <= 5000) {
Loop (i,0,n)
ret_ask(i);
}
Loop (_,0,10) {
auto tmp = ret_ask(rd()%n, 0);
cnt_expen = max(cnt_expen, tmp[0] + tmp[1]);
}
assert(cnt_expen < 500);
solve(0, n, 0, cnt_expen, 0);
}
