#include "prize.h"
#include <bits/stdc++.h>
using namespace std;
mt19937_64 rng(random_device{}());
#define my_random(l,r) uniform_int_distribution<int>(l,r)(rng)
#define my_shuffle(...) shuffle(__VA_ARGS__,rng)
map<int, vector<int>> cache;
map<int, set<int>> S;
int n;
int mx;
vector<int> ASK(int x) {
if(x==-1) return {0, n};
if(x==n) return {n, 0};
if(not cache.contains(x)) cache[x] = ask(x);
S[cache[x][0] + cache[x][1]].insert(x);
return cache[x];
}
int L[200'003];
int R[200'003];
int Left(int x) {
if(x==-1) return 0;
return L[x];
}
int Right(int x) {
if(x==n) return 0;
return R[x];
}
void search(int a, int b) {
if(a>b) return;
int m1=(a+b)>>1, m2=m1;
while(a<m1 && ASK(m1)[0] + ASK(m1)[1] < mx) m1--;
while(m2<b && ASK(m2)[0] + ASK(m2)[1] < mx) m2++;
for(int i=m1; i<=m2; ++i) {
if(a<m1)
L[i]=ASK(m1)[0];
else
L[i]=Left(a-1);
if(m2<b)
R[i]=ASK(m2)[0];
else
R[i]=Right(b+1);
}
if(a<m1 && Left(a-1)<Left(m1)) {
search(a, m1-1);
}
if(m2<b && Right(m2)>Right(b+1)) {
search(m2+1, b);
}
}
int find_best(int _n) {
n = _n;
for(int i=0; i<100; ++i) {
auto v=ASK(my_random(0, n-1));
mx = max(mx, v[0]+v[1]);
}
search(0, n-1);
// for(auto [x, y] : S) {
// cerr << x << ": ";
// for(auto e : y) cerr << e << ' ';
// cerr << endl;
// }
assert(S.begin()->first == 0);
return *(S.begin()->second.begin());
}
