#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;
int found = 0, mx = 0;
void Qry(int p){
if(l[p] != -1) return;
res = ask(p);
l[p] = res[0]; r[p] = res[1];
}
void BS(int L, int R){
if(found) return;
if(R-L < 2) return;
if(l[L] == l[R] && l[L] == l[R]) return;
if(l[L] == 0 && r[L] == 0) found = 1;
int M = (L+R)/2;
Qry(M);
if(l[M] + r[M] != l[L] + r[L] && l[M] + r[M] != l[L] + r[L] && M - 1 > L){
M--;
Qry(M);
if(l[M] + r[M] != l[L] + r[L] && l[M] + r[M] != l[L] + r[L] && M + 2 < R){
M+=2;
Qry(M);
}
}
BS(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;
}
