#include "prize.h"
//author: erray
#include <bits/stdc++.h>
using namespace std;
#ifdef DEBUG
#include "/home/ioi/codes/debug.h"
#else
#define debug(...) (void) 37
#endif
const int J = 9;
const int SMALL = 490;
int find_best(int N) {
vector<int> ll(N, -1), rr(N);
auto Pull = [&](int x) {
if (ll[x] == -1) {
auto g = ask(x);
ll[x] = g[0];
rr[x] = g[1];
}
};
auto L = [&](int x) {
Pull(x);
return ll[x];
};
auto R = [&](int x) {
Pull(x);
return rr[x];
};
auto Rank = [&](int x) {
return L(x) + R(x);
};
int c = 0;
while (c <= N - 1) {
int next = min(N - 1, c + (1 << J));
function<void(int, int)> Dfs = [&](int l, int r) {
if (l == r) {
Pull(l);
return;
}
if (Rank(l) == Rank(r)) {
if (L(r) == L(l)) {
return;
}
int mid = (l + r) >> 1;
Dfs(l, mid);
Dfs(mid, r);
} else if (Rank(l) > Rank(r)) {
Dfs(l, r - 1);
} else {
Dfs(l + 1, r);
}
};
Dfs(c, next);
c = next + 1;
}
int ans = -1;
for (int i = 0; i < N; ++i) {
if (ll[i] != -1 && Rank(i) == 0) {
ans = i;
}
}
debug(ans);
return ans;
}
