#include "prize.h"
#include <bits/stdc++.h>
using namespace std;
vector<int> reduce(vector<int>inds){
if(inds.size()==3){
//iterate
for(int i : inds){
vector<int>quer = ask(i);
if(quer[0]==quer[1]&&quer[0]==0){
vector<int>ans;
ans.push_back(i);
return ans;
}
}
}
int n = inds.size();
int cutoff = 0;
for(int i = 0;i<min(n,600);i++){
vector<int>quer = ask(inds[i]);
cutoff=max(cutoff,quer[0]+quer[1]);
}
//cout << "iterating\n";
//must query among inds and remove worst one and return inds of all that are strictly not greatest in this one
int lo = 0;
int hi = inds.size();
set<int>smaller;
while(1){
lo=0;
if(smaller.size()){
lo=*(--smaller.end())+1;
}
hi=inds.size();
while(lo<hi){
int mid = (lo+hi)/2;
//cout << inds[lo] << " " << inds[mid] << " " << inds[hi] << "\n";
vector<int>quer = ask(inds[mid]);
if(quer[0]+quer[1]<cutoff){
//cout << "hi=mid1\n";
hi=mid;
}
else if(quer[0]>smaller.size()){
//cout << "hi=mid2\n";
hi=mid;
}
else{
//cout << "lo=mid+1\n";
lo=mid+1;
}
}
if(lo==inds.size())
break;
int sz = smaller.size();
smaller.insert(inds[lo]);
if(sz==smaller.size()){
break;
}
//cout << "added: " << inds[lo] << "\n";
}
vector<int>ans;
for(int i : smaller){
ans.push_back(i);
}
return ans;
}
int find_best(int n) {
vector<int>inds(n);
iota(inds.begin(),inds.end(),0);
while(inds.size()>1){
inds=reduce(inds);
}
if(inds.size()!=1){
while(1){
continue;
}
}
return inds[0];
}
