#include "prize.h"
#include<bits/stdc++.h>
using namespace std;
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;
}
void del(vector<int> &vec, int x)
{
for(int i = 0; i < vec.size(); i++) if(vec[i] == x){
vec.erase(vec.begin()+i); return;
}
}
int find_best(int n) {
for(int i = 0; i <= n; i++){sum[i] = -1; cache[i] = {};}
vector<int> candidate;
for(int i = 0; i < n; i++) candidate.push_back(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;
vector<int> x = query(candidate[mid]);
if(x[0] + x[1] == 0){
return candidate[mid]; //We found it
}
if(worst_val == 1e9 || x[0] + x[1] > worst_val){
for(int i : cur_worst){
good.push_back(i); del(candidate, 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(candidate[mid]);
candidate.erase(candidate.begin() + mid);
break;
}
else{
cur_worst.push_back(candidate[mid]);
//Calculate actual left and right
for(int i : good){
if(i < candidate[mid]) 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
}
