#include <vector>
#include <cassert>
#include "prize.h"
using namespace std;
struct Segtree{
vector<int> cache;
Segtree(int n){
cache.resize(4 * n);
}
void buildao(int l, int r, int i){
cache[i] = r-l;
if (l + 1 < r){
int m = l + (r-l)/2;
buildao(l, m, i*2+1);
buildao(m, r, i*2+2);
}
}
int update(int l, int r, int i, int ui, int ux){
if (ui < l || r <= ui) return cache[i];
if (l + 1 == r) return cache[i] = ux;
int m = l + (r-l)/2;
return cache[i] = update(l, m, i*2+1, ui, ux) + update(m, r, i*2+2, ui, ux);
}
int query(int l, int r, int i, int ql, int qr){
if (qr <= l || r <= ql) return 0;
if (ql <= l && r <= qr) return cache[i];
int m = l + (r-l)/2;
return query(l, m, i*2+1, ql, qr) + query(m, r, i*2+2, ql, qr);
}
int findi (int l, int r, int i, int sum){
if (l + 1 == r) {
if (cache[i] > sum) return l;
return r;
}
int m = l + (r-l)/2;
if (cache[i*2+1] > sum) return findi(l, m, i*2+1, sum);
else return findi(m, r, i*2+2, sum - cache[i*2+1]);
}
};
vector<int> queried; int maxsum = 0;
Segtree segtree (1);
int N;
int find(int fake_l, int fake_r, int suml, int sumr, int sumh){
if (fake_l >= fake_r) return -1;
if (fake_l + 1 == fake_r){
int real_l = segtree.findi(0, N, 0, fake_l);
auto ans = ask(real_l);
int l = ans[0], r = ans[1];
if (l + r == 0) return real_l;
else if (l + r > maxsum){
for (int i : queried) segtree.update(0, N, 0, i, 0);
queried = {real_l};
maxsum = l + r;
return -2;
}
else if (l + r < maxsum){
segtree.update(0, N, 0, real_l, 0);
return -1;
}
assert(false);
//return -1;
}
int fake_m = (fake_l + fake_r) / 2;
int real_m = segtree.findi(0, N, 0, fake_m);
auto ans = ask(real_m);
int l = ans[0], r = ans[1];
if (l + r == 0) return real_m;
else if (l + r > maxsum){
for (int i : queried) segtree.update(0, N, 0, i, 0);
queried = {real_m};
maxsum = l + r;
return -2;
}
else if (l + r < maxsum){
segtree.update(0, N, 0, real_m, 0);
if (sumh == -1 || sumh > 1) return find(fake_l, fake_r - 1, suml, sumr, sumh - 1);
return -1;
}
int real_l = segtree.findi(0, N, 0, fake_l), real_r = segtree.findi(0, N, 0, fake_r);
int behindisl = real_m - real_l - segtree.query(0, N, 0, real_l, real_m);
int behindisr = real_r - real_m - 1 - segtree.query(0, N, 0, real_m + 1, real_r);
int al = l - suml - behindisl;
int ar = r - sumr - behindisr;
assert(al + ar == sumh || sumh < 0);
if (al > 0){
int ret = find(fake_l, fake_m, suml, r, al);
if (ret != -1) return ret;
}
if (ar > 0){
int ret = find(fake_m - al - behindisl + 1, fake_r - al - behindisl, l, sumr, ar);
if (ret != -1) return ret;
}
return -1;
}
int find_best(int n){
segtree = Segtree (n);
N = n;
segtree.buildao(0, n, 0);
int ret = -2;
while (ret == -2){
ret = find(0, segtree.cache[0], 0, 0, -1);
}
//assert(ret != -1);
return ret;
}
