#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 = 4e5+100, M = 1e9;
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;
p += n;
T[p]++;
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;
}
set<pii> X, Y;
int qq = 0;
pair<bool, vi> askk(int x){
qq++;
bool flag = false;
if(qq > 9500) assert(false);
vi res = ask(x);
if(res[0] + res[1] == 0) return {flag, {-M, -M}};
if(res[0] + res[1] == sum) flag = true;
Y.insert({x, res[1]});
res[0] -= get(0, x - 1);
res[1] -= get(x + 1, n - 1);
return {flag, res};
}
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 >= 0) q.pb(v[mid - j]);
if(mid + j < (int)v.size()) q.pb(v[mid + j]);
}
bool fine = false;
vi resmid;
int mmid;
vi L, R;
// for(int x: q) cerr << x << ' ';
// cerr << '\n';
for(int x: q){
if(fine){
if(x > mmid) R.pb(x);
else L.pb(x);
continue;
}
auto [flag, res] = askk(x);
if(res[0] == -M) return x;
if(flag){
// 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;
int id = mmid;
if(R.size()) id = R.back();
auto it = Y.lower_bound(pii{id, M});
if(it != Y.end()){
resmid[1] -= ((*it).ss - get((*it).ff + 1, n - 1));
}
if(resmid[0] > 0){
int x = solve(L);
if(x != -1) return x;
}
if(resmid[1] > 0){
int x = solve(R);
if(x != -1) return x;
}
return -1;
}
int find_best(int nn) {
n = nn;
build(n);
for(int j = 0; j < 50; ++j){
int pt = rn(0, n-1);
auto [flag, res] = askk(pt);
if(res[0] == -M) 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);
}
