#include "prize.h"
#include<bits/stdc++.h>
#define ll long long
#define lld long double
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
#define vr(v) v.begin(),v.end()
#define rv(v) v.rbegin(),v.rend()
using namespace std;
namespace RND {
mt19937 myrand(chrono::steady_clock::now().time_since_epoch().count());
ll RANDOM(ll l, ll r) {
ll res = myrand() % (r - l + 1) + l;
return res;
}
void shuffle(vector<int> &a) {
for (int i = 0; i < (int) a.size(); i++) {
int idx = RANDOM(0, (int) a.size() - 1);
swap(a[i], a[idx]);
}
}
};
namespace {
const int N = 2e5 + 5;
int answer = -1;
int A[N][2];
};
void harc(int x) {
if (A[x][0] == -1) {
vector<int> tmp = ask(x);
A[x][0] = tmp[0];
A[x][1] = tmp[1];
}
if (A[x][0] + A[x][1] == 0) {
answer = x;
return;
}
}
int Rank(int x) {
harc(x);
return A[x][0] + A[x][1];
}
int pref(int x) {
harc(x);
return A[x][0];
}
void solve(int start, int end) {
if (answer != -1)return;
if (start == end) {
harc(start);
return;
}
while (Rank(start) != Rank(end)) {
if (Rank(start) < Rank(end))start++;
else end--;
}
if (A[start][0] == A[end][0])return;
int mid = (start + end) >> 1;
solve(start, mid);
solve(mid, end);
}
int find_best(int n) {
for (int i = 0; i < N; i++)A[i][0] = -1;
solve(0, n - 1);
return answer;
}
