#include "prize.h"
#include <bits/stdc++.h>
#define sz 473
#define SIZE 200005
using namespace std;
int chk[SIZE] , ma=-1;
vector<int> ret[SIZE];
vector<int> res;
vector<int> Ask(int p) {
if (chk[p] == 1) return ret[p];
chk[p] = 1;
return ret[p] = ask(p);
}
int S[SIZE] , E[SIZE] , pv;
int f(int s , int e , int x) {
int ans = 0;
while(s <= e) {
int m = (s+e)/2;
if (Ask(m)[0]+Ask(m)[1] != ma) {
ans = m;
e = m-1;
}
else {
if (Ask(m)[0] == x) s = m+1;
else e = m-1;
}
}
return ans;
}
int find_best(int n) {
if (n <= 5000) {
for (int i = 0; i < n; i++) {
if (Ask(i)[0]+Ask(i)[1]==0) return i;
}
return 0;
}
for (int i = 0; i <= sz; i++) {
ma = max(ma , Ask(i)[0]+Ask(i)[1]);
}
S[++pv]=0,E[pv]=0;
for (int i = 1; i < n; i++) {
if (E[pv]-S[pv]+1==sz) S[++pv]=i;
E[pv]=i;
}
int g=1, cnt=0 , prv=-1;
while(g <= pv) {
if (prv >= E[g]) {
g++; continue;
}
if (Ask(E[g])[0]+Ask(E[g])[1]==ma && Ask(E[g])[0]==cnt) {
g++; continue;
}
int p = f(max(prv+1,S[g]) , E[g] , cnt);
res.push_back(p);
cnt++; prv=p;
}
for (auto t : res) if (Ask(t)[0]+Ask(t)[1]==0) return t;
assert(1);
return 0;
}
