#include<bits/stdc++.h>
using namespace std;
#include "prize.h"
// std::vector<int> res = ask(i);
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);
}
constexpr int maxn = 2e5+10;
const vector<int> good = {0, 0};
int bit[maxn];
void upd(int x, int v) {
for(x++; x < maxn; x += x&-x)
bit[x] += v;
}
int query(int x) {
int ans = 0;
for(x++; x > 0; x -= x&-x)
ans += bit[x];
return ans;
}
int find_best(int n) {
int start = 0, base = 0;
// int start = 0, base = 3;
for(int i = 0; i < 10; i++) {
vector<int> a = ask(rnd(n));
base = max(base, a[0]+a[1]);
}
while(1) {
int l = start, r = n-1;
while(1) {
int m = (l+r) >> 1;
vector<int> a = ask(m);
if(a == good) return m;
if(a[0]+a[1] == base) {
if(a[0]-query(m)) r = m-1;
else l = m+1;
} else {
// puts("COMECOU");
upd(m, 1);
int p = m-1;
while(p >= 0) {
vector<int> a = ask(p);
if(a[0]+a[1] == base) {
if(!(a[0]-query(p)))
start = m+1;
break;
}
if(a == good) return p;
upd(p, 1);
--p;
};
// puts("TERMINOU");
// printf("start %d\n", start);
break;
}
}
}
}
