#include "prize.h"
#include <bits/stdc++.h>
using namespace std;
int mx = 0;
int ans = -1;
vector<int> pos;
void search(int ll, int lr, int rl, int rr, int cl, int cr, int c);
void search(int L, int R, int cl, int cr, int c){
if (c == 0) return;
//printf("searching %d %d %d %d %d\n",L,R,cl,cr,c);
if (L == R){
//printf("add pos %d\n",L);
//printf("check: %d\n",g[L]);
pos.push_back(L);
return;
}
if (L > R) return;
int mid = (L+R)/2;
//printf("mid %d\n",mid);
search(L, mid, mid+1, R, cl, cr, c);
return;
}
void search(int ll, int lr, int rl, int rr, int cl, int cr, int c){
if (c == 0) return;
//printf("search <%d,%d><%d,%d>, <%d,%d>, %d\n",ll,lr,rl,rr,cl,cr,c);
if (ll == rr){
search(ll, rr, cl, cr, c);
return;
}
int CL, CR;
int q = (rr-rl)>(lr-ll)?rl:lr;
assert(q >= 0);
vector<int> p = ask(q);
CL = p[0], CR = p[1];
//printf("queried %d, got (%d,%d)\n",q,CL,CR);
if (CL + CR != mx){ /// is special
//printf("add pos %d\n",q);
// printf("check: %d\n",g[q]);
pos.push_back(q);
if (q == lr){
if (ll <= lr-1) search(ll, lr-1, rl, rr, cl, cr, c-1);
else search(rl, rr, cl+1, cr, c-1);
}
else if (q == rl){
if (rl+1 <= rr) search(ll, lr, rl+1, rr, cl, cr, c-1);
else search(ll, lr, cl, cr+1, c-1);
}
return;
}
CR -= cr;
CL -= cl;
if (q == lr){
if (ll <= lr-1) search(ll, lr-1,cl,CR+cr,CL);
search(rl, rr,CL+cl,cr,CR);
}
else{
search(ll, lr,cl,CR+cr,CL);
if (rl+1 <= rr) search(rl+1, rr,CL+cl,cr,CR);
}
}
int find_best(int n) {
for (int i = 0; i < min(n,231); i++){
vector<int> p = ask(i);
//if (p[0] == 0 && p[1] == 0) return i;
mx = max(mx,p[0]+p[1]);
}
int L, R;
L = 0, R = n-1;
int mid = (L+R)/2;
search(L, mid, mid+1, R, 0, 0, mx);
// printf("%d , %d\n",pos.size(),nonmax);
for (auto x : pos){
vector<int> p = ask(x);
if (p[0] + p[1] == 0) return x;
}
assert(false);
}
