#include "prize.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MX = 475;
int X, ret = -1, val[200200];
void dnc(int l, int r, int valL, int valR){
//printf("%d %d %d %d\n", l, r, valL, valR);
int m = (l+r)>>1;
vector<int> v;
while(l<m){
if (val[m]==-1 || val[m]==X){
v = ask(m);
val[m] = v[0]+v[1];
}
if (val[m]!=X){
if (!val[m]) ret = m;
--m;
continue;
}
break;
}
if (l==m){
m = (l+r)>>1;
while(m<r){
if (val[m]==-1 || val[m]==X){
v = ask(m);
val[m] = v[0]+v[1];
}
if (val[m]!=X){
if (!val[m]) ret = m;
++m;
continue;
}
break;
}
}
if (r==m) return;
if (v[0]!=valL) dnc(l, m, valL, v[1]);
if (v[1]!=valR) dnc(m, r, v[0], valR);
}
int find_best(int n) {
fill(val, val+n, -1);
int i;
for (i=0;i<min(n, MX+1);i++){
auto v = ask(i);
X = max(X, v[0]+v[1]);
val[i] = v[0]+v[1];
if (val[i]==0) ret = i;
if (val[i]>=30) break;
}
dnc(i-1, n, i, 0);
assert(ret!=-1);
return ret;
}
