#include "prize.h"
#include <bits/stdc++.h>
using namespace std;
#define sz(x) (int) (x).size()
#define all(x) (x).begin(), (x).end()
#define show(x) cerr << #x << " is " << x << endl;
#define show2(x,y) cerr << #x << " is " << x << " " << #y << " is " << y << endl;
#define show3(x,y,z) cerr << #x << " is " << x << " " << #y << " is " << y << " " << #z << " is " << z << endl;
typedef unsigned long long lint;
typedef pair<lint,lint> ii;
int ans = -1;
int worst = 0;
void dnc(vector<int> stuff, int good, int Lgood, int Rgood){
if(good == 0) return;
if(sz(stuff) == 0) return;
int m = sz(stuff)/2;
auto res = ask(stuff[m]);
if(res[0]+res[1] == 0) ans = stuff[m];
if(res[0]+res[1] == worst){
vector<int> L, R;
for(int i = 0;i < m;i++) L.push_back(stuff[i]);
for(int i = m+1;i < sz(stuff);i++) R.push_back(stuff[i]);
dnc(L, res[0]-Lgood, Lgood, res[1]);
dnc(R, res[1]-Rgood, res[0], Rgood);
}
else{
stuff.erase(stuff.begin()+m);
dnc(stuff, res[0]+res[1]-1, Lgood, Rgood);
}
}
int find_best(int n) {
for(int i = 0;i < min(450,n);i++){
auto res = ask(i);
worst = max(worst,res[0]+res[1]);
}
vector<int> v(n);
for(int i = 0;i < n;i++) v[i] = i;
dnc(v, worst, 0, 0);
return ans;
}
