#include "prize.h"
#include<bits/stdc++.h>
using namespace std;
const int DECA=(1<<18);
int arbre[2*DECA];
int nbquest;
void q(){
nbquest++;
if (nbquest>10000){
while (1>0){
nbquest++;
}
}
}
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++){
q();
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=0;
while (deb<fin){
int mil=(deb+fin+1)/2;
q();
vector<int> quest=ask(mil);
if (quest[0]+quest[1]!=val_maxi){
deb=mil;
fin=mil;
}
else {
if (nbdeb!=quest[0]-somme(deb+DECA, mil+DECA)){
fin=mil-1;
}
else {
deb=mil;
}
}
}
arbre[deb+DECA]+=1;
modif(deb+DECA);
petits.push_back(deb);
vector<int> nouv_encours;
for (auto i:encours){
if (i!=deb){
nouv_encours.push_back(i);
}
}
encours=nouv_encours;
}
int rep=0;
for (auto r:petits){
q();
vector<int> quest=ask(r);
if (quest[0]+quest[1]==0){
rep=r;
}
}
return rep;
}
