#include "prize.h"
#include <bits/stdc++.h>
using namespace std;
int N;
set<int,greater<int>> sat;
int solve(int s, int e, int lv, int rv, int tot){
if(s > e) return -1;
if(lv + rv == tot) return -1;
int m = (s + e)/2;
vector<int> temp = ask(m);
int sum = temp[0] + temp[1];
if(sum == 0) return m;
if(tot < sum){
tot = sum;
int store = solve(0,m - 1, 0, temp[1],tot);
if(store != -1) return store;
return solve(m + 1, N - 1, temp[0], 0,tot);
}
else if(tot == sum){
int store = solve(s,m - 1, lv, temp[1],tot);
if(store != -1) return store;
return solve(m + 1, e, temp[0], rv,tot);
}
else{
for(int i = m + 1; i <= e; i++){
vector<int> temp = ask(i);
int sum = temp[0] + temp[1];
if(sum == 0) return i;
if(sum == tot){
int store = solve(s,m - 1, lv, temp[1] + i - m,tot);
if(store != -1) return store;
return solve(i + 1, e, temp[0], rv,tot);
}
else if(tot < sum){
tot = sum;
int store = solve(0,m - 1, 0, temp[1],tot);
if(store != -1) return store;
return solve(m + 1, N - 1, temp[0], 0,tot);
}
}
for(int i = m - 1; i >= s; i--){
vector<int> temp = ask(i);
int sum = temp[0] + temp[1];
if(sum == 0) return i;
if(sum == tot){
return solve(s, i - 1, lv, temp[1],tot);
}
else if(tot < sum){
tot = sum;
int store = solve(0,m - 1, 0, temp[1],tot);
if(store != -1) return store;
return solve(m + 1, N - 1, temp[0], 0,tot);
}
}
return -1;
}
}
int find_best(int N) {
::N = N;
int s = 0;
int e = N - 1;
return solve(s,e,0,0,-1);
}
