#include "prize.h"
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
#define fr first
#define sc second
map<int,pair<int,pair<int,int>>> qr;
int cnt = 0;
pair<int,pair<int,int>> query(int i) {
if(qr.count(i)) return qr[i];
++cnt;
assert(cnt <= 10000);
vector<int> perg = ask(i);
return qr[i] = mp(perg[0]+perg[1],mp(perg[0],perg[1]));
}
const int B = 500;
int find_best(int n) {
vector<int> esp,lol;
lol.pb(0);
query(0);
for(int i = 1; i < min(n,B); i++) {
if(query(i).fr > query(lol.back()).fr) {
for(auto x : lol) esp.pb(x);
lol.clear();
lol.pb(i);
}
else {
esp.pb(i);
}
}
int i = B;
while(i < n) {
if(query(i).fr != query(lol.back()).fr) {
esp.pb(i);
i++;
continue;
}
lol.pb(i);
int l = i;
int r = n-1;
int nx = -1;
while(l <= r) {
int mid = (l+r)>>1;
if(query(mid).fr != query(i).fr || query(mid).sc.fr != query(i).sc.fr) {
r = mid-1;
}
else {
nx = mid;
l = mid+1;
}
}
i = nx+1;
}
for(auto i : esp) {
if(query(i).fr == 0) return i;
}
assert(false);
return -1;
}
