#include <bits/stdc++.h>
#include "prize.h"
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int int_rand(int a, int b){
return uniform_int_distribution<int>(a, b)(rng);
}
const int TRYMAX = 10, K = 2000;
int maxcnt = 0;
int find_best(int n){
for(int i = 0; i < TRYMAX; i++){
vector<int> vec = ask(int_rand(0, n - 1));
maxcnt = max(maxcnt, vec[0] + vec[1]);
}
vector<bool> ismax(n, false);
int pos = 0, prefix = 0;
while(pos < n){
vector<int> vec = ask(pos);
if(vec[0] + vec[1] != maxcnt) pos++;
int l = pos - 1, r = min(pos + K, n);
while(r - l > 1){
int m = l + (r - l) / 2;
vector<int> vec = ask(m);
if(vec[0] + vec[1] == maxcnt && (m + 1 - vec[0]) - prefix == m - pos + 1) l = m;
else r = m;
}
prefix += (l - pos + 1);
for(int i = pos; i <= l; i++) ismax[i] = true;
pos = max(pos + 1, l + 1);
}
for(int i = 0; i < n; i++){
if(!ismax[i]){
vector<int> vec = ask(i);
if(vec[0] + vec[1] == 0) return i;
}
}
return -1;
}
