#include "prize.h"
#include <bits/stdc++.h>
//#include "grader.cpp"
using namespace std;
//#define int long long
#define ld long double
#define show(x,y) cout << y << " " << #x << endl;
#define show2(x,y,i,j) cout << y << " " << #x << " " << j << " " << #i << endl;
#define show3(x,y,i,j,p,q) cout << y << " " << #x << " " << j << " " << #i << " " << q << " " << #p << endl;
#define show4(x,y) for(auto it:y) cout << it << " "; cout << #x << endl;
typedef pair<int,int>pii;
typedef pair<ld,ld>pi2;
mt19937_64 rng(chrono::system_clock::now().time_since_epoch().count());
int ran(int index){return rng()%index;}
//ask()
int blk=100000;
int sz=450;
int32_t find_best(int32_t n){
pii maxi={-1,-1};
for(int x=0;x<min(n,sz);x++){
vector<int>hold=ask(x);
maxi=max(maxi,{hold[0]+hold[1],x});
if(hold[0]+hold[1]==0) return x;
}
vector<int>nxt=ask(sz);
int cur=sz;
while(cur<n){
vector<int>take=nxt;
if(cur+blk<n) nxt=ask(cur+blk);
else nxt={(int)1e9,(int)1e9};
if(take==nxt&&take[0]+take[1]==maxi.first){
cur+=blk;
continue;
}
int target=min(cur+blk,n);
while(cur<target){
vector<int>check;
if(cur==target-blk) check=take;
else check=ask(cur);
if(check[0]+check[1]==0) return cur;
if(check[0]+check[1]!=maxi.first){
cur++;
continue;
}
if(check==nxt){
cur=target;
continue;
}
int l=cur;
int r=target-1;
int best=l-1;
int mid;
while(l<=r){
mid=(l+r)/2;
vector<int>hold=ask(mid);
if(hold==check){
best=mid;
l=mid+1;
}
else r=mid-1;
}
cur=min(best+1,target);
}
}
return -1;
}
