#include "prize.h"
#include<bits/stdc++.h>
using namespace std;
struct Orz
{
vector<int> bit;
int n, sz = 0;
void init(int nn){
n = nn;
bit.resize(n+1); fill(bit.begin(), bit.end(), 0);
}
void insert(int x)
{
x++; sz++;
for(int i = x; i <= n; i += i & (-i)) bit[i] += 1;
}
void erase(int x)
{
x++; sz--;
for(int i = x; i <= n; i += i & (-i)) bit[i] -= 1;
}
int find_by_order(int x)
{
int p = 0;
for(int i = __lg(n); i >= 0; i--){
int p2 = p + (1 << i);
if(p2 <= n && bit[p2] <= x){x -= bit[p2]; p = p2;}
}
return p;
}
int order_of_key(int x)
{
int ans = 0; x++;
for(int i = x; i > 0; i -= i & (-i)) ans += bit[i];
return ans-1;
}
int size(){return sz;}
void clear(){sz = 0;}
};
int n, bit[200005];
void update(int p, int v)
{
p++;
for(int i = p; i <= n; i += i & (-i)) bit[i] += v;
}
int query(int p)
{
p++;
int ans = 0;
for(int i = p; i > 0; i -= i & (-i)) ans += bit[i];
return ans;
}
vector<int> cache[200005];
int sum[200005];
vector<int> askvec(int p)
{
vector<int> &ans = cache[p];
if(ans.size() == 0) ans = ask(p);
sum[p] = ans[0] + ans[1];
return ans;
}
Orz candidate;
vector<int> good, cur_worst;
int worst_val = 1e9;
bool forced_return = 0;
void dfs(int l, int r, int suffix)
{
if(l > r) return;
//Be careful when update candidate
int mid = (l+r)/2, cur = candidate.find_by_order(mid), curr = candidate.find_by_order(r);
//cerr<<"A"<<l<<" "<<r<<" "<<suffix<<endl;
//for(int i = l; i <= r; i++) cerr<<candidate.find_by_order(i)<<" ";
//cerr<<endl;
bool is_new = (sum[cur] == -1);
vector<int> x = askvec(cur); int s = x[0] + x[1];
if(s == 0){good.push_back(cur); candidate.clear(); forced_return = 1; return;}
if(worst_val == 1e9 || s > worst_val){
//Update the worst val and return immediately
for(int i : cur_worst){
good.push_back(i); update(i, 1); candidate.erase(i);
}
worst_val = s; cur_worst = {cur}; forced_return = 1; return;
}
else if(s < worst_val){
//cerr<<"D"<<l<<" "<<r<<endl;
good.push_back(cur); update(cur, 1); candidate.erase(cur); return; //We might continue dfs
}
else{
if(is_new == 1) cur_worst.push_back(cur);
vector<int> y = x;
y[0] -= query(cur-1); y[1] -= query(curr)-query(cur) + suffix;
while(y[0] > 0){
int re = y[0];
//cerr<<"B"<<y[0]<<endl;
int m = candidate.order_of_key(cur) - 1;
dfs(l, m, x[1]);
if(forced_return == 1) return;
y[0] = x[0] - query(cur-1);
if(y[0] == re) break;
}
while(y[1] > 0){
int re = y[1];
//cerr<<"C"<<y[1]<<" "<<suffix<<endl;
int m = candidate.order_of_key(cur) + 1, nr = candidate.order_of_key(curr);
dfs(m, nr, suffix);
if(forced_return == 1) return;
y[1] = x[1] - (query(curr)-query(cur)) - suffix;
if(y[1] == re) break;
}
}
}
int find_best(int nn) {
n = nn;
for(int i = 0; i <= n; i++){bit[i] = 0; sum[i] = -1; cache[i] = {};}
candidate.init(n);
for(int i = 0; i < n; i++) candidate.insert(i);
//Repeatedly find a non-lollipop prize
good.clear(); cur_worst.clear();
worst_val = 1e9;
while(candidate.size() > cur_worst.size()){
forced_return = 0;
dfs(0, candidate.size()-1, 0);
//cerr<<"____________________________"<<endl;
}
for(int i : good) if(sum[i] == 0) return i;
return -1; //This should never happen
}
