#include "prize.h"
#include <bits/stdc++.h>
using namespace std;
int i,s=1,pos,l,r;
vector <int> v[200001];
set <pair <int,int> > myset;
int find_best(int n) {
v[1]=ask(1);
for (i=1;i<=475;i++) {
v[i]=ask(i-1);
if ((v[i][0]+v[i][1])==0)
return i-1;
if ((v[s][0]+v[s][1])<=(v[i][0]+v[i][1]))
s=i;
}
for (i=n;i>0;i--) {
if (!(v[i].size()))
v[i]=ask(i-1);
if ((v[i][0]+v[i][1])==0)
return i-1;
if ((v[s][0]+v[s][1])==(v[i][0]+v[i][1]))
break;
}
myset.insert({v[s][0],s});
myset.insert({v[i][0],i});
while (true){
pos=s;
l=(*(--(myset.upper_bound({v[s][0],200001})))).second;
r=(*(myset.upper_bound({v[s][0]+1,0}))).second;
for (i=17;i>=0;i--) {
if (pos+(1<<i)>=r)
continue;
pos+=(1<<i);
if (pos<=l)
continue;
if (!(v[pos].size()))
v[pos]=ask(pos-1);
if ((v[pos][0]+v[pos][1])!=(v[s][0]+v[s][1])) {
if ((v[pos][0]+v[pos][1])==0)
return pos-1;
pos-=(1<<i);
continue;
}
myset.insert({v[pos][0],pos});
if (v[pos][0]>v[s][0])
pos-=(1<<i);
}
for (i=pos+1;i<=n;i++) {
if (!(v[i].size()))
v[i]=ask(i-1);
if ((v[i][0]+v[i][1])==0)
return i-1;
if ((v[i][0]+v[i][1])==(v[s][0]+v[s][1]))
break;
}
s=i;
myset.insert({v[s][0],s});
}
}
