#include "prize.h"
#include <bits/stdc++.h>
using namespace std;
const int LOG = 18, TAKE = 400;
int find_best(int n) {
int mn = 1e9, 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;
}
mn = min(mn, s);
}
while(id < n){
// find next smallest num
for(; id < n; id++){
auto c = ask(id);
int s = c[0] + c[1];
if(s == 0){
return id;
}
if(s == mn){
cnt = c[0];
break;
}
}
// overjump all min
for(int j = 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 == mn && c[0] == cnt){
id += jump;
}
}
// go to the next which is not min
id++;
}
assert(false);
}
/*
5516
*/
