#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;
int cntnonlol;
int n;
pair<int,pair<int,int>> query(int i) {
if(i == n) return mp(cntnonlol,mp(cntnonlol,0));
if(qr.count(i)) return qr[i];
++cnt;
// assert(cnt <= 8500);
vector<int> perg = ask(i);
return qr[i] = mp(perg[0]+perg[1],mp(perg[0],perg[1]));
}
const int B = 477;
const int S = 600;
int find_best(int N) {
n = N;
vector<int> esp,lol;
lol.pb(0);
query(0);
for(int i = 1; i < min(n,B); i++) {
if(query(i).fr == 0) return i;
if(query(i).fr > query(lol.back()).fr) {
for(auto x : lol) {
if(query(x).fr == 0) return x;
esp.pb(x);
}
lol.clear();
lol.pb(i);
}
else {
esp.pb(i);
if(query(i).fr == 0) return i;
}
}
cntnonlol = query(lol.back()).fr;
vector<pair<int,int>> lr;
for(int l = B; l < n; l+= S) {
lr.pb(mp(l,min(l+S-1,n-1)));
}
while(lr.size()) {
int l = lr.back().fr;
int r = lr.back().sc;
lr.pop_back();
while(l <= r && query(l).fr != query(lol.back()).fr) {
if(query(l).fr == 0) return l;
esp.pb(l);
l++;
}
while(l <= r && query(r).fr != query(lol.back()).fr) {
if(query(r).fr == 0) return r;
esp.pb(r);
r--;
}
if(l > r) continue;
if(query(l).sc.fr == query(r).sc.fr) continue;
int mid = (l+r)/2;
lr.pb(mp(l,mid));
lr.pb(mp(mid+1,r));
}
// 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 = min(i+S-1,n-1);
// if(query(i).fr == query(r).fr && query(i).sc.fr == query(r).sc.fr) {
// i = r+1;
// continue;
// }
// int nx = -1;
// while(l <= r) {
// int mid = (l+r)/2;
// 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;
}
