#include "prize.h"
#include <bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
using namespace std;
const int MAXN = 2e5+10;
typedef pair<int,int> pii;
int n;
pii ASK(int i){
vector<int> res = ask(i);
return {res[0], res[1]};
}
int find_best(int N) {
n = N;
// if(n <= 500){
// for(int i = 0; i < n; i++) {
// vector<int> res = ask(i);
// if(res[0] + res[1] == 0)
// return i;
// }
// return 0;
// }
set <int> s;
for(int i=0; i<min(n, 500); i++){
vector<int> ret = ask(i);
if(ret[0] + ret[1] == 0)
return i;
s.insert(ret[0] + ret[1]);
}
if(s.size() > 5) assert(false);
int MX = *(--s.end());
int nw = 0;
while(true){
// cout << nw << " nw\n";
pii ret = ASK(nw);
if(ret.fi + ret.se == 0)
return nw;
int more = ret.se;
if(ret.fi+ret.se != MX){
nw++; continue;
}
int l=nw+1, r=n-1, mid=0, cnt=nw;
while(l<=r){
mid = (l+r)>>1;
pii ret = ASK(mid);
if(ret.fi + ret.se == 0)
return mid;
if(ret.se == more) cnt = mid, l = mid+1;
else r = mid-1;
}
nw = cnt+1;
}
}
