#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) {
//assert(sumh == 0);
return -1;
}
if (sumh == 0) 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);
int middle = 1;
fake_r--;
for (int dev = 1;; ++dev) {
if (fake_m < fake_r) {
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;
if (l + r > maxsum) {
for (int i : queried) segtree.update(0, N, 0, i, 0);
queried = {real_m};
maxsum = l + r;
return -2;
}
if (l + r == maxsum){
int r1 = find(fake_l, fake_m, suml, r + middle, l - suml - middle);
int r2 = find(fake_m + 1 - (l - suml - middle), fake_r - (l - suml - middle), l, sumr, r - sumr);
if (r1 != -1) return r1;
return r2;
}
segtree.update(0, N, 0, real_m, 0);
middle++;
fake_r--;
}
else {
return find(fake_l, fake_m, suml, sumr + middle, sumh - middle);
}
}
}
int real_l = segtree.findi(0, N, 0, fake_l), real_r = segtree.findi(0, N, 0, fake_r);
int donel = real_m - real_l - segtree.query(0, N, 0, real_l, real_m), doner = real_r - real_m - 1 - segtree.query(0, N, 0, real_m + 1, real_r);
int al = l - suml - donel;
int ar = r - sumr - doner;
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 + 1, fake_r - al, l, sumr, ar);
if (ret != -1) return ret;
}
return -1;
}
int find_best(int n){
segtree = Segtree (n);
N = n;
queried.clear();
maxsum = 0;
segtree.buildao(0, n, 0);
int ret = -2;
while (ret == -2){
ret = find(0, segtree.cache[0], segtree.findi(0, N, 0, 0), N - segtree.findi(0, N, 0, segtree.cache[0] - 1) - 1, -1);
}
//assert(segtree.cache[0] + maxsum == N);
return ret;
}
