// M
#include<bits/stdc++.h>
#include "prize.h"
using namespace std;
const int N = 200005;
int n, GRes, MX;
vector < int > A[N];
inline void Ask(int i)
{
if (!A[i].size())
A[i] = ask(i);
}
void Solve(int l, int r, int k, int le = 0, int ri = 0)
{
//printf("%d :: %d :: %d\n", l, r, k);
if (r <= l || k == 0)
return ;
if (GRes != -1)
return ;
if (r - l == 1)
{
Ask(l);
if (A[l][0] + A[l][1] == 0)
GRes = l;
return ;
}
int md1 = (l + r) >> 1;
int md2 = md1;
int cc = 0;
while (md2 < r)
{
Ask(md2);
if (A[md2][0] + A[md2][1] == 0)
{
GRes = md2;
return ;
}
if (A[md2][0] + A[md2][1] == MX)
break;
cc ++;
assert(cc <= k);
md2 ++;
}
if (md2 == r)
{
Solve(l, md1, k - cc, le, ri + cc);
return ;
}
Solve(l, md1, k - cc - (A[md2][1] - ri), le, cc + A[md2][1]);
Solve(md2 + 1, r, A[md2][1] - ri, A[md2][0], ri);
}
int find_best(int _n)
{
n = _n;
if (n <= 4000)
{
for (int i = 0; i < n; i ++)
{
vector < int > TMp = ask(i);
if (TMp[0] + TMp[1] == 0)
return i;
}
}
int SQ = 449;
MX = 0;
int opt = -1;
for (int i = 0; i < SQ; i ++)
{
Ask(i);
if (A[i][0] + A[i][1] == 0)
return i;
if (MX <= A[i][0] + A[i][1])
MX = A[i][0] + A[i][1], opt = i;
}
GRes = -1;
Solve(opt + 1, n, A[opt][1]);
return GRes;
}
