#include <stdio.h>
#include <vector>
#include <queue>
#include <algorithm>
#include <iostream>
#include <string>
#include <bitset>
#include <map>
#include <set>
#include <tuple>
#include <string.h>
#include <math.h>
#include <random>
#include <functional>
#include <assert.h>
#include <math.h>
#include "prize.h"
#define all(x) (x).begin(), (x).end()
#define xx first
#define yy second
using namespace std;
template<typename T, typename Pr = less<T>>
using pq = priority_queue<T, vector<T>, Pr>;
using i64 = long long int;
using ii = pair<int, int>;
using ii64 = pair<i64, i64>;
vector<ii> finded;
int bigSize;
random_device rd;
mt19937 mt(rd());
int cnt(int l, int r)
{
return upper_bound(all(finded), ii{ r, 1 << 30 }) - lower_bound(all(finded), ii{ l, -1 });
}
bool test(int n, int l, int r)
{
if (l > r)
return false;
int m = (l + r) / 2;
int ml = m;
int mlL = 0, mlR = 0;
while (ml >= l)
{
if (any_of(all(finded), [ml](ii x) { return x.xx == ml; }))
{
ml--;
continue;
}
auto res = ask(ml);
if (res[0] + res[1] != bigSize)
{
finded.insert(lower_bound(all(finded), ii{ ml, res[0] + res[1] }), ii{ ml, res[0] + res[1] });
if (res[0] + res[1] == 0)
return true;
ml--;
}
else
{
mlL = res[0];
mlR = res[1];
break;
}
}
if (ml > l && mlL != cnt(0, ml - 1))
if (test(n, l, ml - 1))
return true;
if (m + 1 <= r && mlR - (m - ml) != cnt(m + 1, n - 1))
if (test(n, m + 1, r))
return true;
return false;
}
int find_best(int n)
{
vector<int> indexs(n);
for (int i = 0; i < n; i++)
indexs[i] = i;
shuffle(all(indexs), mt);
vector<ii> ix;
for (int i = 0; i < min(n, 30); i++)
{
auto q = ask(indexs[i]);
ix.emplace_back(q[0] + q[1], indexs[i]);
}
sort(all(ix));
bigSize = ix.back().xx;
test(n, 0, n - 1);
for (auto& [k, v] : finded)
{
if (v == 0)
return k;
}
return 0;
}
