#include "prize.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define pii pair<int,int>
#define ff first
#define cerr if(false) cerr
#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, summ;
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;
}
void assertt(bool x){
if(!x){
cerr <<" failn" << endl;
vector<int> v;
for(int j = 0; j < 1000000000; ++j){
v.push_back(j);
}
}
}
set<pii> X, Y;
int qq = 0;
pair<bool, pair<vi, vi>> askk(int x, bool is){
qq++;
bool flag = false;
if(qq > 9500) assert(false);
vi res = ask(x);
if(res[0] + res[1] == 0) return {flag, {{-M, -M}, {-M, -M}}};
if(res[0] + res[1] == summ) flag = true;
vi ress = res;
if(is && flag){
Y.insert({x, res[1]});
}
res[0] -= get(0, x - 1);
res[1] -= get(x + 1, n - 1);
return {flag, pair<vi,vi>{res, ress}};
}
int solve(vi v){
if(v.empty()) assertt(false);
for(int x: v) cerr << x << ' ';
cerr << '\n';
cerr << '\n';
int mid = (int)v.size()/2;
int pt = v[mid];
vi q;
q.pb(v[mid]);
for(int j = 1; j < mid + 15; ++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, resmidd;
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 p = askk(x, true);
bool flag = p.ff;
vi res = p.ss.ff;
vi res2 = p.ss.ss;
if(res[0] == -M) return x;
if(flag){
// we can split now..
fine = true;
resmid = res;
resmidd = res2;
mmid = x;
}else{
upd(x, 1);
--sum; // decrease sum
}
}
if(!fine){
// none here lol
return -1;
}
sort(all(R));
sort(all(L));
int id = v.back();
reverse(all(R));
vi RR;
fine = false;
for(int x: R){
if(fine){
RR.pb(x);
continue;
}
auto p = askk(x, true);
bool flag = p.ff;
vi res = p.ss.ff;
vi res2 = p.ss.ss;
if(res[0] == -M) return x;
if(flag){
fine = true;
resmid[1] -= res[1];
}else{
upd(x, 1);
}
}
R = RR;
sort(all(R));
// auto it = Y.lower_bound(pii{id, M});
// // cerr << id << ' ' << resmidd[1] << ' ';
// if(it != Y.end()){
// // cerr << (*it).ff << ' ' << (*it).ss << ' ' << get(mmid + 1, (*it).ff) << " creep ";
// resmid[1] = resmidd[1] - (*it).ss - get(mmid + 1, (*it).ff);
// // resmid[1] -= ((*it).ss - get((*it).ff + 1, n - 1));
// }
// cerr << mmid << ' ' << resmid[0] << ' ' << resmid[1] << " f\n";
if(resmid[0] > 0){
int x = solve(L);
if(x != -1) return x;
}
if(R.size()){
assertt(R.size());
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 p = askk(pt, false);
bool flag = p.ff;
vi res = p.ss.ff;
vi res2 = p.ss.ss;
// 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);
summ = sum;
return solve(v);
}
