#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>
const int N = 2e5+100;
int n, T[2*N+5];
void build(int sz){
for(int j = 0; j <= 2*sz + 5; ++j) T[j] = 0;
}
void add(int 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;
r += n + 1;
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 solve(int l, int r){
int mid = l+r>>1;
vi res = ask(mid);
if(res[0] + res[1] == 0) return mid;
vi resL = ask(l);
vi resR = ask(r);
res[0] -= resL[0];
res[1] -= resR[1];
// X.insert({mid, res[0]});
// Y.insert({mid, res[1]});
// auto it = Y.upper_bound(pii{mid, N});
// if(it != Y.end()) res[1] -= (*it).ss;
// auto it2 = X.upper_bound(pii{mid, -1});
// if(it2 != X.begin()) res[0] -= (*prev(it2)).ss;
// now we know what do we got in our boundary at least...
if(res[0]){
int x = solve(l, mid - 1);
if(x != -1) return x;
}
if(res[1]){
int x = solve(mid + 1, r);
if(x != -1) return x;
}
return -1;
}
int find_best(int nn) {
n = nn;
return solve(0, n-1);
}
