#include "prize.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define pii pair<int,int>
#define ff first
#define ss second
#define vi vector<int>
#define all(x) x.begin(),x.end()
const int N = 2e5+100;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int rn(int l, int r){
return uniform_int_distribution<int>(l,r)(rng);
}
int n, T[2*N+5], sum = 0;
void build(int sz){
for(int j = 0; j <= 2*sz + 5; ++j) T[j] = 0;
}
void upd(int p, int val){
++p;
T[p += n]++;
for(p >>= 1; p; p >>= 1) T[p] = T[p<<1] + T[p<<1|1];
}
int get(int l, int r){
int res = 0;
l += n + 1;
r += n + 2;
for(; l < r; l >>= 1, r >>= 1){
if(l&1) res += T[l++];
if(r&1) res += T[--r];
}
return res;
}
int qq = 0;
vi askk(int x){
qq++;
if(qq > 9500) assert(false);
vi res = ask(x);
if(res[0] + res[1] == 0) return {-1, -1};
res[0] -= get(0, x - 1);
res[1] -= get(x + 1, n - 1);
return res;
}
set<pii> X, Y;
int solve(vi &v){
if(v.empty()) return -1;
int mid = (int)v.size()/2;
int pt = v[mid];
vi q;
q.pb(v[mid]);
for(int j = 1; j < mid + 5; ++j){
if(mid + j < (int)v.size()) q.pb(v[mid + j]);
if(mid - j >= 0) q.pb(v[mid - j]);
}
bool fine = false;
vi resmid;
int mmid;
vi L, R;
for(int x: q){
if(fine){
if(x > mmid) R.pb(x);
else L.pb(x);
continue;
}
vi res = askk(x);
if(res[0] == -1) return x;
if(res[0] + res[1] == sum){
// we can split now..
fine = true;
resmid = res;
mmid = x;
}else{
upd(x, 1);
--sum; // decrease sum
}
}
if(!fine){
// none here lol
return -1;
}
sort(all(R));
sort(all(L));
fine = false;
vi resright;
reverse(all(R));
vi RR;
for(int x: R){
if(fine){
RR.pb(x);
continue;
}
vi res = askk(x);
if(res[0] == -1) return x;
if(res[0] + res[1] == sum){
// we can split now..
fine = true;
resright = res;
}else{
upd(x, 1);
--resmid[1];
--sum; // decrease sum
}
}
sort(all(RR));
if(resright.size())
resmid[1] -= resright[1];
if(resmid[0] > 0){
int x = solve(L);
if(x != -1) return x;
}
if(resmid[1] > 0){
int x = solve(RR);
if(x != -1) return x;
}
return -1;
}
int find_best(int nn) {
n = nn;
build(n);
for(int j = 0; j < 20; ++j){
int pt = rn(0, n-1);
vi res = askk(pt);
// if(res[0] == -1) return pt;
if(sum < res[0] + res[1])
sum = res[0] + res[1];
}
vi v;
for(int j = 0; j < n; ++j) v.pb(j);
return solve(v);
}
