#include "prize.h"
#include <bits/stdc++.h>
using namespace std;
const int LOG = 18, TAKE = 500;
int find_best(int n) {
// find max
int mx = 0;
for(int i = 0; i < min(TAKE, n); i++){
auto c = ask(i);
int s = c[0] + c[1];
if(s == 0) return i;
mx = max(mx, s);
}
function<int(int, int)> find = [&](int l , int r){
int cntl = 0, cntr = 0;
for(; 1; l++){
auto c = ask(l);
int s = c[0] + c[1];
if(s == 0) return l;
cntl = c[0];
if(s == mx){
break;
}
}
for(; 1; r--){
auto c = ask(r);
int s = c[0] + c[1];
if(s == 0) return r;
cntr = c[0];
if(s == mx){
break;
}
}
if(cntl != cntr){
int m = (l + r) / 2;
int ret;
if((ret = find(l, m)) != -1){
return ret;
}
if((ret = find(m + 1, r)) != -1){
return ret;
}
}
return -1;
};
return find(0, n - 1);
}
