#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=290;
map<int,vector<int>>mp;
vector<int>f(int index){
if(mp.find(index)!=mp.end()) return mp[index];
return mp[index]=ask(index);
}
int32_t find_best(int32_t n){
vector<int>nxt=f(0);
int cur=0;
while(cur<n){
vector<int>take=nxt;
if(cur+blk<n) nxt=f(cur+blk);
else nxt={(int)1e9,(int)1e9};
if(take==nxt){
cur+=blk;
continue;
}
int target=min(cur+blk,n);
int counter2=0;
while(cur<target){
counter2++;
vector<int>check;
if(cur==target-blk) check=take;
else check=f(cur);
if(check[0]+check[1]==0) return cur;
if(check==nxt){
cur=target;
continue;
}
int l=cur+1;
int r=target-1;
int best=r;
int mid;
int counter=0;
while(l<=r){
counter++;
mid=(l+r)/2;
vector<int>hold=f(mid);
if(hold==check){
l=mid+1;
}
else{
best=mid;
if(hold[0]+hold[1]==0) return mid;
r=mid-1;
}
}
cur=min(best+1,target);
}
}
return -1;
}
