#include "prize.h"
#include <bits/stdc++.h>
//#define int long long
#define pii pair<int,int>
#define vi vector<int>
#define ff first
#define ss second
#define sp << " " <<
#define all(x) x.begin(),x.end()
using namespace std;
const int inf = 2e9;
int find_best(int n) {
set<int> possible;
int mx = 0;
srand(time(0));
int select;
for (int i = 0;i<50;i++) {
int r = rand()%n;
vi g = ask(r);
if (g[0]+g[1] > mx) {
mx = g[0]+g[1];
select = r;
}
if (g[0]+g[1] == 0) return r;
}
for (int i=0;i<n;i++) possible.insert(i);
int pl = select,pr = select;
while (1) {
vector<int> q = ask(pl);
int l = 0;
int r = pl-1;
while (l<=r) {
int m = (l+r) >> 1;
vi vv = ask(m);
if (vv[0]+vv[1] == 0) return m;
if (vv[0] < q[0]) l = m+1;
else r = m-1;
}
if (r == -1) break;
possible.erase(r);
pl = r;
}
while (1) {
vector<int> q = ask(pr);
int l = pr+1;
int r = n-1;
while (l<=r) {
int m = (l+r) >> 1;
vi vv = ask(m);
if (vv[0]+vv[1] == 0) return m;
if (vv[1] < q[1]) r = m-1;
else l = m+1;
}
if (l == n) break;
possible.erase(l);
pl = r;
}
for (auto it : possible) {
vi vv = ask(it);
if (vv[0] + vv[1] == 0) return it;
}
assert(0);
}
