#include "prize.h"
#include<bits/stdc++.h>
using namespace std;
struct fenwick
{
int n;
vector < int > T;
fenwick(int n_)
{
n = n_ + 1;
T.resize(n);
}
void add(int i, int v)
{
for (int k = i+1; k < n; k+=k&-k) T[k] += v;
}
int query(int i)
{
int ans = 0;
for (int k = i+1; k; k -= k&-k) ans += T[k];
return ans;
}
};
int find_best(int n) {
map < int , map < int , int > > queried;
queue < pair < int , int > > toq;
toq.emplace(0, n);
fenwick ignore(n);
while(!toq.empty())
{
auto [l, r] = toq.front();
toq.pop();
int m = (l+r)/2;
if (l >= r) continue;
if (ignore.query(m) > 0) continue;
auto res = ask(m);
int left = res[0], right = res[1];
int key = left+right;
if (key == 0)
return m;
auto &occ = queried[key];
{
auto it = occ.upper_bound(m);
if (it != occ.end() && it->second == left)
{
while(it != occ.end() && it->second == left) it++;
it--;
int x = m, y = it->first;
ignore.add(y, 1);
ignore.add(x, -1);
}
}
{
auto it = occ.upper_bound(m);
if (it != occ.begin())
{
it--;
while(it->second == left && it != occ.begin()) it--;
it++;
if (it->second == left && it->first < m)
{
int x=it->first, y = m;
ignore.add(y, 1);
ignore.add(x, -1);
}
}
}
toq.emplace(l, m);
toq.emplace(m, r);
occ[m] = left;
}
return 0;
}
