#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){
vector<int> a = ask(l);
if(a[0] + a[1] == 0) ans = l;
return;
}
int mid = (l + r)/2;
vector<int> 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 >= l) solve(l, (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 >= l && (a[0] + a[1] < lol); mid --){
a = ask(mid);
if(a[0] + a[1] == 0){
ans = mid;
return;
}
}
mid ++;
if(mid - 1 >= l) solve(l, mid - 1, a[0] - ll, lol, ll, a[1]);
}
int find_best(int n) {
ans = -1;
int ll = -1, rr = -1, maxx = 0, mid = (n - 1)/2, br1 = 0, br2 = 0, br = 0, br3 = 0, br4 = 0;
for(int i = mid; i < min(n, mid + 250); i++){
vector<int> a = ask(i);
if(a[0] + a[1] == 0) return i;
if(a[0] + a[1] > maxx){
br3 = a[0];
br4 = a[1];
maxx = a[0] + a[1];
rr = i;
br = 1;
}else if(a[0] + a[1] == maxx){
br++;
rr = i;
br3 = a[0];
br4 = a[1];
}
}
bool ok = true;
for(int i = mid - 1; i >= max(0, mid - 250); 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];
ll = i;
br = 1;
ok = false;
}else if(a[0] + a[1] == maxx){
br++;
ll = i;
br1 = a[0];
br2 = a[1];
}
}
if(ok){
if(ll != -1){
if(ll - 1 >= 0)solve(0, ll - 1, br1, maxx, 0, br2);
if(rr + 1 <= n - 1) solve(rr + 1, n - 1, br4, maxx, br3, 0);
}else{
if(rr + 1 <= n - 1) solve( rr + 1, n - 1, br4, maxx, br3, 0);
if(mid - 250 - 1 >= 0) solve(0, mid - 250 - 1, br3 - (rr - mid + 250 - br), maxx, 0, br4 + (rr - mid + 250 - br));
}
}else{
if(ll - 1 >= 0) solve(0, ll - 1, br1, maxx, 0, br2);
if(mid + 250 <= n - 1) solve(mid + 250, n - 1, br2 - (mid + 250 - ll - br), maxx, br1 + (mid + 250 - ll - br), 0);
}
return ans;
}
