#include "prize.h"
using namespace std;
#include <vector>
int z,r,y;
bool e;
vector<int> g;
bool f(int a,int b){
if (e){return false;}
if (g[a]==g[b]){
return false;
}
vector<int> p={-1,-1};
if (a+1==b){
p=ask(a);
if (p==(vector<int>){0,0}){
r=a;
return true;
}
if (p[0]+p[1]>z){
e=true;
z=p[0]+p[1];
}
return false;
}
int m=(a+b)/2;
while ((p[0]+p[1])!=z){
if (m==b){
p[0]=g[b];
g[m-1]=g[b]-1;
m++;
break;
}
p=ask(m);
if (p[0]==0&&p[1]==0){
r=m;
return true;
}
if (p[0]+p[1]>z){
e=true;
z=p[0]+p[1];
return false;
}
m++;
}
m--;
if (m!=b){
g[m]=p[0];
}
g[(a+b)/2]=p[0]-m+(a+b)/2;
if (f(a,(a+b)/2)){
return true;
}
if (f(m,b)){
return true;
}
return false;
}
int find_best(int n) {
g.resize(n);
g[0]=0;
z=ask(n-1)[0];
if (z==0){
return n-1;
}
g[n-1]=z;
y=n-1;
e=false;
f(0,n-1);
vector<int> p;
while (e){
y--;
p=ask(y);
if (p[0]+p[1]==0){
return y;
}
if (p[0]+p[1]>z){
z=p[0]+p[1];
}
if (p[0]+p[1]==z){
g[y]=p[0];
e=false;
f(0,y);
}
}
return r;
}
