#include<bits/stdc++.h>
#include "prize.h"
using namespace std;
int find_best(int n) {
int cnt = 0, id = 0, cnR = 0;
for(int i = 0; i < min(n, 473); i++) {
vector<int> v = ask(i);
if(!v[0] && !v[1]) return i;
if(cnt <= v[0] + v[1]) {
cnt = v[0] + v[1];
cnR = v[1];
id = i;
}
}
while(true) {
int l = id + 1, r = n - 1, nxt = 0;
while(l <= r) {
int mid = (l + r) / 2;
vector<int> v = ask(mid);
if(!v[0] && !v[1]) return mid;
if(v[0] + v[1] != cnt) {
nxt = mid;
r = mid - 1;
continue;
}
if(v[1] == cnR) {
l = mid + 1;
} else r = mid - 1;
}
assert(nxt);
id = nxt;
while(true) {
++id;
vector<int> v = ask(id);
if(!v[0] && !v[1]) return id;
if(v[0] + v[1] == cnt) break;
}
}
}
