#include "prize.h"
#include<bits/stdc++.h>
using namespace std;
const int DECA=(1<<18);
int arbre[2*DECA];
int somme(int a, int b){
if (a==b){
return arbre[a];
}
if (a%2==1){
return arbre[a]+somme(a+1, b);
}
if (b%2==0){
return somme(a,b-1)+arbre[b];
}
return somme(a/2, b/2);
}
void modif(int a){
while (a>1){
a/=2;
arbre[a]=arbre[2*a]+arbre[2*a+1];
}
}
int find_best(int n) {
int val_maxi=0;
for (int i=0;i<min(n,500);i++){
vector<int> quest=ask(i);
val_maxi = max(val_maxi, quest[0]+quest[1]);
}
int nb_petits=val_maxi;
vector<int> encours;
for (int i=0;i<n;i++){
encours.push_back(i);
}
vector<int> petits;
for (int i=0;i<nb_petits;i++){
int deb=0, fin=encours.size()-1;
int nbdeb=somme(DECA, encours[0]+DECA);
while (deb<fin){
int mil=(deb+fin+1)/2;
vector<int> quest=ask(encours[mil]);
if (quest[0]+quest[1]!=val_maxi){
deb=mil;
fin=mil;
}
else {
if (nbdeb!=quest[0]-somme(encours[deb]+DECA, encours[mil]+DECA)){
fin=mil-1;
}
else {
nbdeb=quest[0];
deb=mil;
}
}
}
arbre[encours[deb]+DECA]+=1;
modif(encours[deb]+DECA);
petits.push_back(encours[deb]);
vector<int> nouv_encours;
for (auto a:encours){
if (a!=encours[deb]){
nouv_encours.push_back(a);
}
}
encours=nouv_encours;
}
int rep=0;
for (auto r:petits){
vector<int> quest=ask(r);
if (quest[0]+quest[1]==0){
rep=r;
}
}
return rep;
}
