#include "prize.h"
#include <bits/stdc++.h>
#define pb push_back
using namespace std;
const int maxn = 2e5 + 10;
int asked[maxn], ansl[maxn], ansr[maxn];
vector < int > a;
void goask(int i)
{
if(asked[i])
{
return;
}
a = ask(i);
asked[i] = 1;
ansl[i] = a[0];
ansr[i] = a[1];
}
int find_best(int n)
{
int maxsum = 0;
for (int i = 0; i < min(n, 750); ++ i)
{
goask(i);
int bigger = ansl[i] + ansr[i];
if(bigger > maxsum)maxsum = bigger;
}
int start = 0, passed = 0;
for (int run = 1; run < n; ++ run)
{
int l = start, r = n-1, mid, res = 0;
while(l <= r)
{
mid = (l + r)/2;
goask(mid);
int onl = ansl[mid];
int onr = ansr[mid];
int total = onl + onr;
if(total == 0)return mid;
if(total != maxsum)
{
r = mid - 1;
}
else if(onl == passed)
{
l = mid + 1;
}
else
{
r = mid - 1;
res = mid;
}
}
for (int i = res + 1; i < n; ++ i)
{
goask(i);
int total = ansl[i] + ansr[i];
if(total == 0)return i;
if(total == maxsum)
{
start = i;
}
else
{
passed ++;
}
}
}
return n-1;
}
