#include "prize.h"
#include <bits/stdc++.h>
#define pb push_back
#define F first
#define S second
#define all(x) x.begin(), x.end()
using namespace std;
typedef pair<int, int> pii;
const int N = 2e5 + 10;
pii A[N];
pii Ask(int i){
if(A[i] != pii(-1, -1)) return A[i];
vector<int> res = ask(i - 1);
pii tmp = {res[0], res[1]};
return A[i] = tmp;
}
int mx;
vector<int> V;
int fen[N];
void Add(int idx, int d){
//if(d == -1) cerr << "--- " << idx << '\n';
for(; idx < N; idx += idx & -idx)
fen[idx] += d;
}
int Get(int idx){
int res = 0;
for(; idx; idx -= idx & -idx)
res += fen[idx];
return res;
}
int Get0(int L, int R){
if(R < L) return 0;
return (R - L + 1) - (Get(R) - Get(L - 1));
}
int Bin(int x){
int res = 0, res2;
for(int lg = 18; lg >= 0; lg--){
res2 = res | (1 << lg);
if(res2 >= N) continue;
if(fen[res2] < x){
x -= fen[res2];
res = res2;
}
}
return res + 1;
}
struct fun {
int L, R, bl, br, rq;
fun (int _L, int _R, int _bl, int _br, int _rq){
L = _L;
R = _R;
bl = _bl;
br = _br;
rq = _rq;
}
};
vector< fun > slv;
int find_best(int n) {
fill(A, A + n, pii(-1, -1));
memset(fen, 0, sizeof fen);
mx = -1; V.clear();
for(int i = 1; i <= n; i++) Add(i, 1);
pii fst = Ask(n / 2);
mx = fst.F + fst.S;
V = {n / 2};
slv.pb( fun(1, n, 0, 0, mx) );
int L, R;
while(!slv.empty()){
fun la = slv.back();
slv.pop_back();
//cerr << "! " << la.L << ' ' << la.R << " : " << la.rq << '\n';
if(la.rq == 0) continue;
L = la.L;
R = la.R;
int sm = Get(R) - Get(L - 1);
assert(sm >= la.rq);
int mid = Bin(Get(L - 1) + ((sm + 1) / 2));
//cerr << "# " << mid << '\n';
pii tmp = Ask(mid);
//
if(tmp.F + tmp.S > mx){
mx = tmp.F + tmp.S;
for(auto x : V) Add(x, -1);
V.clear();
slv.clear();
slv.pb(fun(1, n, 0, 0, Get(N - 1)));
continue;
}
if(tmp.F + tmp.S == mx){
int c0 = Get0(L, mid - 1);
//cerr << "c0 : " << c0 << '\n';
slv.pb(fun(L, mid - 1, la.bl, tmp.S, tmp.F - la.bl - c0));
slv.pb(fun(mid + 1, R, tmp.F, la.br, la.rq - (tmp.F - la.bl - c0)));
//slv.pb({{L, mid - 1}, });
//slv.pb({{mid + 1, R}, });
continue;
}
Add(mid, -1);
//slv.pb(la);
slv.pb(fun(L, R, la.bl, la.br, la.rq - 1));
}
for(int i = 1; i <= n; i++)
if(A[i] == pii(0, 0))
return i - 1;
assert(false);
return 0;
}
