#include <bits/stdc++.h>
#include "prize.h"
#define vi vector<int>
#define vvi vector<vi>
#define vb vector<bool>
#define vvb vector<vb>
#define ii pair<int, int>
#define x first
#define y second
#define vii vector<ii>
#define pb push_back
#define all(x) x.begin(), x.end()
#define loop(i,s,e) for(int i=s;i<e;++i)
#define chkmax(a,b) a = max(a,b)
#define chkmin(a,b) a = min(a,b)
using namespace std;
map<int, ii> qur;
int cnt = 0, maxcnt = 9999;
ii myask(int i){
//cout<<"QUR: "<<i<<endl;
if (qur.find(i)!=qur.end()) return qur[i];
if (cnt++==maxcnt) loop(j,0,1) j--;
vi res = ask(i);
return qur[i] = {res[0], res[1]};
}
int mrand(){
return rand() ^ (rand()<<15);
}
int find_best(int n) {
cnt = 0; qur.clear();
int worst = 3;
set<int> ss; //free querys
loop(i,0,0){
int ind = abs(mrand())%n;
ii res = myask(ind);
chkmax(worst, res.x+res.y);
if (res.x+res.y==0) return ind;
ss.insert(ind);
}
loop(i,0,n){
ii res = myask(i);
if (res.x+res.y!=worst){
if (res.x+res.y==0) return i;
continue;
}
int l = i+1, r = n, mid, ans=-1;
while(l<r){
mid = (l+r) / 2;
auto it = ss.lower_bound(l);
if (it!=ss.end() && *it<r) mid = *it;
else ss.insert(mid);
//cout<<"HI: "<<i<<" "<<mid<<endl;
ii tmp = myask(mid);
if (tmp.x+tmp.y==0) return mid;
if (tmp.x+tmp.y!=worst) ans = mid, r = mid;
else{
if (tmp.x > res.x) r = mid;
else l = mid + 1;
}
}
if (ans==-1) break;
//cout<<"I: "<<i<<" "<<ans<<endl;
i = ans;
}
return 0;
}
/*
clear
g++ prize.cpp grader.cpp -o a ; ./a
8
3 2 3 3 3 2 3 1
*/
