#include "prize.h"
#include <bits/stdc++.h>
using namespace std;
int MAX = 500;
int v;
map<int, vector<int>> memo;
vector<int> qry(int i){
if(memo.count(i)) return memo[i];
vector<int> a = ask(i);
return memo[i] = a;
}
int ans = -1;
void solve(int l, int r, int subL, int subR){
if(r < l) return;
int m = (l+r)/2;
int lo = m-1, hi = m;
int it = 0;
int cnt = 0;
while(true){
if(ans != -1) return;
if(it == 0) m = hi++;
else m = lo--;
if(lo < l && hi > r) break;
if(m < l || m > r) continue;;
vector<int> a = qry(m);
if(a[0]+a[1] == 0){
ans = m;
return;
}
if(a[0]+a[1] != v){
cnt++;
continue;
}
if(it == 0){
if(cnt < a[0]-subL) solve(l, lo, subL, cnt+a[1]);
if(0 < a[1]-subR) solve(hi, r, a[0]+cnt, subR);
}
else{
if(0 < a[0]-subL) solve(l, lo, subL, cnt+a[1]);
if(cnt < a[1]-subR)solve(hi, r, a[0]+cnt, subR);
}
}
}
int find_best(int n) {
MAX = min(n, MAX);
v = 0;
for(int i = 0; i < MAX; i++){
vector<int> a = qry(i);
if(a[0] + a[1] == 0) return i;
v = max(v, a[0]+a[1]);
}
solve(0, n-1, 0, 0);
return ans;
}
