#include "prize.h"
#include <bits/stdc++.h>
using namespace std;
const int MAXN = (int) 2e5;
static bool mark[MAXN];
vector <int> qry[MAXN];
inline vector <int> myask(int pos) {
if(mark[pos] == 0) {
qry[pos] = ask(pos);
}
mark[pos] = 1;
return qry[pos];
}
int find_best(int n) {
srand(time(NULL));
auto myrand = [&]() {
return (1LL * (1LL << 15) * rand() + rand()) % n;
};
vector <bool> vis(n);
int i, mx = 0;
for(i = 0; i < 30 && i < n; i++) {
int cur = myrand();
while(vis[cur]) {
cur = myrand();
}
vector <int> a = ask(cur);
mx = max(mx, a[0] + a[1]);
vis[cur] = 1;
}
int num = n - mx;
i = 0;
while(i < n) {
vector <int> a = myask(i);
if(a[0] + a[1] == 0) {
return i;
}
if(a[0] + a[1] < mx) {
while(1) {
a = ask(++i);
if(a[0] + a[1] == 0) {
return i;
}
if(a[0] + a[1] == mx) break;
}
}
else {
int l = a[0], r = a[1];
int res = 0;
for(int step = 1 << 17; step; step >>= 1) {
if(i + res + step < n && num >= res + step + 1) {
a = ask(i + res + step);
if(a[0] == l && a[1] == r) {
res += step;
}
}
}
i += res + 1;
num -= (res + 1);
}
}
assert(0);
}
