#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;
ii myask(int i){
//cout<<"QUR: "<<i<<endl;
if (qur.find(i)!=qur.end()) return qur[i];
vi res = ask(i);
return qur[i] = {res[0], res[1]};
}
int mrand(){
return rand() ^ (rand()<<15);
}
int find_best(int n) {
int worst = 0;
loop(i,0,100){
ii res = myask(abs(mrand())%n);
chkmax(worst, res.x+res.y);
}
//cout<<"HI: "<<endl;
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;
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 1 3 3 2 3
*/
