#include "prize.h"
#include <bits/stdc++.h>
#define ll long long
#define F first
#define S second
#define pii pair<int, int>
const int mod = 1e9 + 7;
const int mxN = 2e3 + 5;
const int mnN = 1e9 * -1;
using namespace std;
vector<vector<int>> res;
int find_best(int n) {
res.resize(n);
if (n <= 5000)
{
for(int i = 0;i < n;i++){
res[i] = ask(i);
if(res[i][0] + res[i][1] == 0) return i;
}
}
int mx = 0;
for(int tmp = 0; tmp < 20;tmp++){
int md = rand() % n;
if(res[md].empty()) res[md] = ask(md);
mx = max(res[md][0] + res[md][1], mx);
}
int s = 0,e = n - 1;
while(1){
if(res[s].empty()) res[s] = ask(s);
if(res[s][0] + res[s][1] != mx){
if(res[s][0] + res[s][1] == 0) return s;
s++;
continue;
}
int num = res[s][0];
int l = s - 1,r = e,md;
while(l < r){
md = (l + r + 1) / 2;
if(res[md].empty())res[md] = ask(md);
if(res[md][0] + res[md][1] == 0) return md;
if(res[md][0] + res[md][1] != mx || res[md][0] != num){
r = md - 1;
}else l = md;
}
l++;
if(res[l].empty()) res[l] = ask(l);
if (res[l][0] + res[l][1] == 0) return l;
s = l + 1;
}
}
