#include<bits/stdc++.h>
using namespace std;
#include "prize.h"
std::mt19937 rng(std::chrono::steady_clock::now().time_since_epoch().count() ^ (long long) (make_unique<char>().get()));
template<typename T> T rnd(T v) {
T k = (T) rng();
return (T) (((k % v) + v) % v);
}
#define pb push_back
#define sz(a) (int)((a).size())
const vector<int> good = {0, 0};
constexpr int maxn = 2e5;
int base, N;
int solve(vector<int>& v, int l, int r) {
if(!sz(v)) return -1;
// assert(l+r != base);
if(sz(v) == 1) {
if(ask(v[0]) == good) return v[0];
return -1;
}
// printf("l, r == %d %d, b, e == %d %d\n", l, r, v[0], v.back());
// printf("l, r == %d %d %d %d %d\n", l, r, v[0], v.back(), sz(v));
// for(int x : v)
// printf("%d ", x);
// printf("\n");
int m = sz(v)/2;
vector<int> a, b;
for(int i = 0; i < m; i++)
a.pb(v[i]);
vector<int> res = ask(v[m]);
if(res == good) return v[m];
if(res[0]+res[1] == base) {
// printf("v %d\n", v[m]);
for(int i = m; i < sz(v); i++)
b.pb(v[i]);
if(res[0] - l) {
int ans = solve(a, l, res[1]);
if(ans != -1) return ans;
}
if(r - res[1]) {
int ans = solve(b, res[0], r);
if(ans != -1) return ans;
}
} else {
int seen = 1, p = v[m]+1;
bool ok = 0;
while(p <= v.back()) {
// printf("p %d\n", p);
res = ask(p);
if(res == good) return p;
if(res[0]+res[1] == base) {
for(int i = p+1; i <= v.back(); i++)
b.pb(i);
if(res[0] - l - seen) {
int ans = solve(a, l, res[1]+seen);
if(ans != -1) return ans;
}
if(r - res[1]) {
int ans = solve(b, res[0], r);
if(ans != -1) return ans;
}
ok = 1;
break;
}
++p, ++seen;
}
if(!ok) {
// // assert(0);
// // Isso vai dar errado mas quero ver até aonde vai
// // Depois é só fazer o meio andar pra esquerda tbm
// assert(ask(v.back()+1)[0]+ask(v.back()+1)[1] == base);
// int r = seen+(v.back()==N-1?0:(ask(v.back()+1)[1]));
// // if(r + l != base) {
// int ans = solve(a, l, r);
// if(ans != -1) return ans;
// // }
a.clear();
p = v[m]-1;
while(p >= v[0]) {
res = ask(p);
if(res == good) return p;
if(res[0]+res[1] == base) {
if(res[0]-l) {
int ans = solve(a, l, seen+res[1]);
if(ans != -1) return ans;
}
break;
}
++seen, --p;
}
}
}
return -1;
}
int find_best(int n) {
N = n;
int last = 0;
for(int i = 0; i < 50; i++) {
int pos = rnd(n);
// printf("%d\n", pos);
vector<int> opa = ask(pos);
base = max(base, opa[0]+opa[1]);
}
// for(int i = 0; i < min(475, n); i++) {
// vector<int> opa = ask(i);
// // if(opa == good) return i;
// if(opa[0]+opa[1] >= base)
// base = opa[0]+opa[1];
// }
vector<int> a;
for(int i = 0; i < n; i++)
a.pb(i);
return solve(a, 0, 0);
}
