#include "prize.h"
#include<bits/stdc++.h>
using namespace std;
/*I actually copied these lines from g4g. In an actual competition I will code a walk on BIT myself*/
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
vector<int> cache[200005];
int sum[200005];
vector<int> query(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 n) {
for(int i = 0; i <= n; i++){sum[i] = -1; cache[i] = {};}
ordered_set candidate;
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 = query(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);
}
bool ok = (cur_worst.size() > 0);
cur_worst.clear(); worst_val = x[0] + x[1];
if(ok == 1) break;
}
else if(x[0] + x[1] < worst_val){
good.push_back(cur);
candidate.erase(cur);
break;
}
else{
cur_worst.push_back(cur);
//Calculate actual left and right
for(int i : good){
if(i < cur) x[0]--;
else x[1]--;
}
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
}
