#include <bits/stdc++.h>
using namespace std;
#define x first
#define y second
#define lg length()
#define pb push_back
#define INF 2000000005
#define LINF 1000000000000000005
#define all(x) (x).begin(), (x).end()
#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define sz(x) (int)(x).size()
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int rand(int l,int r){return uniform_int_distribution<int>(l,r)(rng);}
#include "prize.h"
vector<int> l,r;
vector<int> res;
void Qry(int p){
res = ask(p);
l[p] = res[0]; r[p] = res[1];
}
void BS(int L, int R){
if(R-L < 2) return;
int M = (L+R)/2;
Qry(M);
if(l[L] + r[L] != l[M] + r[M] || l[L] != l[M]) BS(L, M);
if(l[R] + r[R] != l[M] + r[M] || l[R] != l[M]) BS(M, R);
}
int find_best(int n) {
l.resize(n, -1);
r.resize(n, -1);
Qry(0); Qry(n-1);
BS(0, n-1);
for(int i=0;i<n;i++){
if(l[i] == 0 && r[i] == 0) return i;
}
return 0;
}
