#include "prize.h"
#include <bits/stdc++.h>
using namespace std;
const int LOG = 18, TAKE = 500;
int find_best(int n) {
int mx = 0, id;
// last apperance of num and cnt
map<int, int> last;
for(id = 0; id < min(TAKE, n); id++){
auto c = ask(id);
int s = c[0] + c[1];
last[s] = c[0];
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];
last[s] = c[0];
if(s == 0){
return id;
}
if(s == mx){
break;
}
}
int jump_point = 7;
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(last.count(s) && c[0] == last[s]){
ok = 0;
last[s] = c[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(last.count(s) && c[0] == last[s]){
id += jump;
last[s] = c[0];
}
}
// go to the next which is not max
id++;
}
assert(false);
}
