#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;
vector<int> memo[200005];
bool isgood[200005];
bool tried[200005];
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;
int cnt = 0;
for(int i = 0;i < sz(stuff);i++){
int x = stuff[i];
if(tried[x] and not isgood[x]) i = m;
}
int orim = m;
if(cnt == good) return;
while(m < sz(stuff)){
vector<int> res;
if(tried[stuff[m]]) res = memo[stuff[m]];
else 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 < orim;i++) L.push_back(stuff[i]);
for(int i = m+1;i < sz(stuff);i++) R.push_back(stuff[i]);
int btwgood = m-orim;
dnc(L, res[0]-Lgood-btwgood, Lgood, res[1]+btwgood);
dnc(R, res[1]-Rgood-btwgood, res[0]+btwgood, Rgood);
return;
}
else m++;
}
vector<int> L;
int btwgood = sz(stuff) - m;
for(int i = 0;i < orim;i++) L.push_back(stuff[i]);
dnc(L, good-btwgood, Lgood, Rgood+btwgood);
}
int find_best(int n) {
int taken = 0;
while(taken < min(n, 500)){
int i = rand()%n;
if(tried[i]) continue;
tried[i] = 1;
vector<int> res = ask(i);
memo[i] = res;
worst = max(worst,res[0]+res[1]);
if(res[0]+res[1] == 0) ans = i;
taken++;
}
if(ans != -1) return ans;
for(int i = 0;i < n;i++){
if(tried[i]) isgood[i] = (memo[i][0]+memo[i][1] != worst);
}
vector<int> v;
for(int i = 0;i < n;i++){
v.push_back(i);
}
dnc(v, worst, 0, 0);
return ans;
}
