#include "prize.h"
#include <bits/stdc++.h>
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int rand(int l , int r){
return rng() % (r-l+1) + l;
}
int find_best(int n) {
map < int , vector<int>>mpa;
auto query = [&](int x){
// cout << "query : " << x << endl;
if(mpa.count(x))return mpa[x];
else return mpa[x] = ask(x);
};
// find the maximum by random sampling
const int M = 50;
int maxi = 0;
for(int i = 0;i<M;i++){
vector < int > res = query(rand(0,n-1));
maxi = max(maxi , res[0] + res[1]);
}
// cout << "DONE" << endl;
auto check = [&](vector < int > &a){// check whether it is the biggest one
return maxi == a[0] + a[1];
};
// iterate over the non biggest ones
int cur = 0;
while(cur < n){
vector < int > res = query(cur);
if(check(res)){// it is one of the biggest ones , make it not
vector < int > myres = res;
// cout << "myres : " << myres[0] << " " << myres[1] << endl;
if(myres[1] == 0)break;
int l = cur+1 , r = n;
while(l < r){
int mid = (l + r) / 2;
vector < int > midres = query(mid);
// cout << mid << " midres : " << midres[0] << " " << midres[1] << endl;
if(check(midres) == 0){
cur = mid;
r = mid;
}
else if(midres[0] - myres[0])r = mid;
else l = mid+1;
}
res = query(cur);
}
// cout << "cur : " << cur << endl;
if(res[0] + res[1] == 0)return cur;
cur++;
}
return -1;
}
