#include "prize.h"
#include <bits/stdc++.h>
using namespace std;
//#include "grader.cpp"
pair <int, int> memo[200001];
int ans;
pair <int, int> get (int x) {
if (memo[x].first != -1) {
return memo[x];
}
auto h = ask(x);
pair <int, int> g = {h[0], h[1]};
if (g.first + g.second == 0) {
ans = x;
}
return memo[x] = g;
}
void solve (int l, int r) {
if (l == r) {
get(l);
return;
}
auto less = [&] (int x, int y) -> bool {
return get(x).first + get(x).second < get(y).first + get(y).second;
};
while (less(l, r) || less(r, l)) {
while (less(l, r)) l++;
while (less(r, l)) r--;
}
if (get(l).second == get(r).second) {
return;
}
int mid = (l + r) / 2;
solve(l, mid); solve(mid + 1, r);
}
int find_best (int n) {
ans = -1;
for (int i = 0; i < n; i++) {
memo[i] = {-1, -1};
}
solve(0, n - 1);
return ans;
}
