#include "prize.h"
#include<bits/stdc++.h>
using namespace std;
struct Orz
{
vector<int> bit;
int n, sz = 0;
Orz(int n): n(n){
bit.resize(n+1);
}
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 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;
}
int find_best(int nn) {
n = nn;
for(int i = 0; i <= n; i++){bit[i] = 0; sum[i] = -1; cache[i] = {};}
Orz candidate(n);
for(int i = 0; i < n; i++) candidate.insert(i);
//Repeatedly find a non-lollipop prize
vector<int> good, cur_worst;
int worst_val = 1e9;
while(candidate.size() > 0){
int l = 0, r = candidate.size()-1;
while(l <= r){
int mid = (l+r)/2, cur = candidate.find_by_order(mid);
vector<int> x = askvec(cur);
if(x[0] + x[1] == 0){
return cur; //We found it
}
if(worst_val == 1e9 || x[0] + x[1] > worst_val){
for(int i : cur_worst){
good.push_back(i); candidate.erase(i); update(i, 1);
}
bool ok = (cur_worst.size() > 0);
cur_worst.clear(); worst_val = x[0] + x[1];
if(ok == 1) break;
else if(x[0] == 0) l = mid+1;
else r = mid-1;
}
else if(x[0] + x[1] < worst_val){
good.push_back(cur); update(cur, 1);
candidate.erase(cur);
break;
}
else{
cur_worst.push_back(cur);
//Calculate actual left and right
x[0] -= query(cur); x[1] -= good.size() - query(cur);
if(x[0] == 0 && x[1] == 0){candidate.clear(); break;} //No more improvement
else if(x[0] == 0) l = mid+1;
else r = mid-1;
}
}
}
for(int i : good) if(sum[i] == 0) return i;
return -1; //This should never happen
}
