#include "prize.h"
#include <bits/stdc++.h>
using namespace std;
const int LOG = 18, TAKE = 750;
int find_best(int n) {
int mx = 0, id, cnt = 0;
for(id = 0; id < min(TAKE, n); id++){
auto c = ask(id);
int s = c[0] + c[1];
if(s == 0){
return id;
}
mx = max(mx, s);
}
while(id < n){
// find next biggest num
for(; id < n; id++){
auto c = ask(id);
int s = c[0] + c[1];
if(s == 0){
return id;
}
if(s == mx){
cnt = c[0];
break;
}
}
// test 7 if not jump all
int jump_point = 10;
bool ok = 1;
int jump = 1<<jump_point;
if(id + jump < n){
auto c = ask(id + jump);
int s = c[0] + c[1];
if(s == 0){
return id + jump;
}
if(s == mx && c[0] == cnt){
ok = 0;
}
}
// overjump all biggest
for(int j = (ok ? jump_point - 1 : LOG); j >= 0; j--){
int jump = 1<<j;
if(id + jump >= n){
continue;
}
auto c = ask(id + jump);
int s = c[0] + c[1];
if(s == 0){
return id + jump;
}
if(s == mx && c[0] == cnt){
id += jump;
}
}
// go to the next which is not max
id++;
}
assert(false);
}
/*
5516
*/
