#include "prize.h"
#include<bits/stdc++.h>
#define out(x) #x<<" = "<<x<<" "
using namespace std;
int ans;
vector<int> a;
void solve(int l, int r, int br, int lol, int ll, int rr){
//cout<<out(l)<<out(r)<<out(br)<<out(lol)<<endl;
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;
}
if(a[0] + a[1] == lol){
if(mid - 1 >= l) solve(l, mid - 1, a[0] - ll, lol, ll, a[1]);
if(mid + 1 <= r) solve(mid + 1, r, a[1] - rr, lol, a[0], rr);
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;
}
}
mid--;
if(a[0] + a[1] == lol){
if((l + r)/2 - 1 >= 0) solve(0, (l + r)/2 - 1, a[0] - (mid - (l + r)/2) - ll, lol, ll, a[1] + mid - (l + r)/2);
if(mid + 1 <= r) solve(mid + 1, r, a[1] - rr, lol, a[0], rr);
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;
}
}
mid ++;
if(mid - 1 >= 0) solve(0, mid - 1, a[0] - ll, lol, ll, a[1]);
}
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 + 300); 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];
maxx = a[0] + a[1];
x = i;
}
}
for(int i = mid - 1; i >= max(0, mid - 300); 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];
maxx = a[0] + a[1];
x = i;
}
}
if(x != 0 && br1 != 0) solve(0, x - 1, br1, maxx, 0, br2);
if(x != n - 1 && br2 != 0) solve(x + 1, n - 1, br2, maxx, br1, 0);
return ans;
}
