#include <bits/stdc++.h>
#include "prize.h"
using namespace std;
const int bont = 1200;
int ert = 0;
int megold(int l, int r, vector<int> ansl, vector<int> ansr){
if(l+1 >= r) return -1;
//cout<<l<<" "<<r<<"\n";
int m1 = (l+r)/2;
int m2 = m1;
vector<int> ans = ask(m1);
if(ans[0] + ans[1] == 0) return m1;
vector<int> ans2 = ans;
while(m1-1 > l && ans[0]+ans[1] != ert){
m1--;
ans = ask(m1);
if(ans[0] + ans[1] == 0) return m1;
}
while(m2+1 < r && ans2[0]+ans2[1] != ert){
m2++;
ans2 = ask(m2);
if(ans2[0] + ans2[1] == 0) return m2;
}
return max((ansl[0] < ans[0] ? megold(l, m1, ansl, ans) : -1), (ans2[0] < ansr[0] ? megold(m2, r, ans2, ansr) : -1));
}
int find_best(int n) {
int s = 500;
for(int i = 0; i < min(n, 500); i++){
vector<int> ans = ask(i);
if(ans[0]+ans[1] == 0) return i;
ert = max(ert, ans[0]+ans[1]);
}
while(s < n){
vector<int> ans = ask(s);
if(ans[0]+ans[1] == 0)
return s;
while(ans[0]+ans[1] != ert){
s++;
ans = ask(s);
if(ans[0]+ans[1] == 0)
return s;
}
int e = min(s+bont, n-1);
int s2 = e+1;
vector<int> ans2 = ask(e);
if(ans2[0]+ans2[1] == 0)
return e;
while(s < e && ans2[0]+ans2[1] != ert){
e--;
ans2 = ask(e);
if(ans2[0]+ans2[1] == 0)
return e;
}
if(ans[0] < ans2[0]){
int temp = megold(s, e, ans, ans2);
if(temp != -1)
return temp;
/*int l = s, r = e;
while(l+1 < r){
int m = (l+r)/2;
vector<int> ans3 = ask(m);
if(ans3[0]+ans3[1] == 0) return m;
if(ans3[0]+ans3[1] != ert || ans3[0] != ans[0])
r = m;
else
l = m;
}
s = l+2;
ans = ask(s);
if(ans[0]+ans[1] == 0) return s;
while(s < e && ans[0]+ans[1] != ert){
s++;
ans = ask(s);
if(ans[0]+ans[1] == 0)
return s;
}*/
}
s = s2;
}
return -1;
}
