#include <bits/stdc++.h>
#include "prize.h"
#define all(x) (x).begin(),(x).end()
using namespace std;
using ll = long long;
using ld = long double;
//#define int ll
#define sz(x) ((int)(x).size())
using pii = pair<int,int>;
using tii = tuple<int,int,int>;
const int K = 500;
const int nmax = 2e5 + 5;
int dimmax = 0;
int L[nmax * 2], R[nmax * 2];
int found = -1;
void fake(int x) {
if(L[x] == -1) {auto v = ask(x - 1); L[x] = v[0]; R[x] = v[1]; }
if(L[x] == 0 && R[x] == 0) found = x - 1;
}
int queryS(int x) {
fake(x);
return L[x] + R[x];
}
int queryL(int x) {
fake(x);
return L[x];
}
int queryR(int x) {
fake(x);
return R[x];
}
#define lsb(x) (x & -x)
namespace AIB {
int tree[2 * nmax];
int len;
void softinit(int nlen) { len = nlen; }
void upd(int p, int x) {
while(p <= len) tree[p] += x, p += lsb(p);
return;
}
int conv(int p) {
int sum = 0;
while(p > 0) sum += tree[p], p -= lsb(p);
return sum;
}
int deconv(int p) {
p--;
//cerr << "need to " << p << ' ';
int lim = 0;
for(int i = 18; i >= 0; i--) {
if(lim + (1 << i) > len) continue;
if(p >= tree[lim + (1 << i)])
p -= tree[lim + (1 << i)], lim += (1 << i);
}
//cerr << lim + 1 << '\n';
//if(lim == 5) {
//cerr << "(\n";
//for(int j = 1; j <= len; j++)
//cerr << conv(j) - conv(j - 1) << ' ';
//cerr << ")\n";
//}
return lim + 1;
}
void init() {
for(int i = 1; i <= len; i++) upd(i, 1);
}
}
#define mkcheck { if(found != -1) return found; }
using AIB::deconv;
using AIB::conv;
#define n ajsd
int n;
int getR(int x) {
return (n - x) - (AIB::conv(n) - AIB::conv(x));
}
int find_best(int N) {
n = N;
AIB::softinit(N * 2);
AIB::init();
for(int i = 0; i < 2 * n; i++) L[i] = -1;
bool fiter = 1;
auto deactivate = [&](int x) {AIB::upd(x, -1); };
for(int l = 1, r = min(n, K); l <= n; l += K, r = min(r + K, n)) {
if(fiter) {
fiter = 0;
for(int j = l; j <= r; j++)
dimmax = max(queryS(j), dimmax);
for(int i = n + 1; i <= 2 * n; i++)
L[i] = dimmax, R[i] = 0;
for(int j = l; j <= r; j++)
if(queryS(j) != dimmax)
deactivate(j);
}
else {
//cerr << l << " --> " << r << '\n';
int t = conv(r) + 1;
while(queryS(deconv(t)) != dimmax) deactivate(t); mkcheck;
t = deconv(t);
//cerr << '\t' << t << '\t';
int nl = AIB::conv(l - 1) + 1;
//cerr << nl << '\n';
while(deconv(nl) <= r && queryS(deconv(nl)) != dimmax) deactivate(deconv(nl)); mkcheck;
//cerr << deconv(nl) << '\n';
if(deconv(nl) <= r) {
//cerr << queryR(deconv(nl)) - queryR(t) << '\n';
for(int smth = 0; smth < queryR(deconv(nl)) - queryR(t); smth++) {
int tmp = nl, base = deconv(nl);
//cerr << queryR(base) << ' ' << deconv(nl) << " -> ";
int ptrt = conv(t);
bool ok = 0;
for(int i = 9; i >= 0; i--) {
if(nl + (1 << i) >= ptrt) continue;
int u = deconv(nl + (1 << i));
//cerr <<"?" << u << ' ' << queryR(u) << '\t';
if(queryS(u) != dimmax) { ok = 1; deactivate(u); mkcheck; break; }
if(queryR(u) >= queryR(base) - smth) nl += (1 << i);
}
if(!ok) {
nl++;
//cerr << "!!" << deconv(nl) << '\n';
deactivate(deconv(nl));
}
nl = tmp;
//cerr << "--\n";
}
}
}
//cerr << "=====\n";
mkcheck;
}
mkcheck;
assert(false);
return -1;
}
#undef n
/**
Anul asta se da centroid.
-- Surse oficiale
*/
