#include "prize.h"
#include<bits/stdc++.h>
using namespace std;
int ans;
vector<int> a;
void solve(int l, int r, int br, int lol){
if(br == 0) return;
if(ans != -1) return;
if(l == r){
a = ask(l);
if(a[0] + a[1] == 0) ans = l;
return;
}
int mid = (l + r)/2;
a = ask(mid);
if(a[0] + a[1] == 0){
ans = mid;
return;
}
for(mid = mid + 1; mid <= r && (a[0] + a[1] < lol); mid++){
a = ask(mid);
if(a[0] + a[1] == 0){
ans = mid;
return;
}
}
if(a[0] + a[1] == lol){
if((l + r)/2 - 1 >= 0) solve(0, (l + r)/2 - 1, a[0] - (mid - (l + r)/2), lol);
if(mid + 1 <= r) solve(mid + 1, r, a[1], lol);
return;
}
for(mid = (l + r)/2 - 1; mid >= 0 && (a[0] + a[1] < lol); mid --){
a = ask(mid);
if(a[0] + a[1] == 0){
ans = mid;
return;
}
}
if(mid - 1 >= 0) solve(0, mid - 1, a[0], lol);
}
int find_best(int n) {
ans = -1;
int x = -1, maxx = 0, mid = (n - 1)/2, br1 = 0, br2 = 0;
for(int i = mid; i < min(n, mid + 255); i++){
vector<int> a = ask(i);
if(a[0] + a[1] == 0) return i;
if(a[0] + a[1] >= maxx){
br1 = a[0];
br2 = a[1];
x = i;
}
}
for(int i = mid - 1; i >= max(0, mid - 255); i--){
vector<int> a = ask(i);
if(a[0] + a[1] == 0) return i;
if(a[0] + a[1] >= maxx){
br1 = a[0];
br2 = a[1];
x = i;
}
}
if(x != 0) solve(0, x - 1, br1, maxx);
if(x != n - 1) solve(x + 1, n - 1, br2, maxx);
return ans;
}
