#include "prize.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair < int , int >
#define fi first
#define se second
#define FOR(i, a, b) for (int i = (a), _b = (b); i <= _b; i ++)
#define FORD(i, a, b) for (int i = (a), _b = (b); i >= _b; i --)
#define REP(i, n) for (int i = 0, _n = (n); i < _n; i ++)
#define bit(x, i) (((x) >> (i)) & 1ll)
#define mask(x) (1ll << (x))
#define mem(f, x) memset(f, x, sizeof(f))
#define sz(x) (int32_t) (x.size())
void myAssert(bool a) {
while (!a) {
assert(-1 == 1);
}
}
const int nmax = 2e5;
vector < int > sv[nmax + 7], val;
int cnt = 1, used[nmax + 7];
set < int > spos;
vector < int > myAsk(int i) {
if (sv[i].empty()) {
++ cnt;
myAssert(cnt <= 10000);
sv[i] = ask(i);
int sum = sv[i][0] + sv[i][1];
bool ok = 1;
for (auto x: val) {
if (x == sum) {
ok = 0;
}
}
spos.insert(i);
if (ok) {
val.push_back(sum);
sort(val.begin(), val.end(), greater < int > ());
}
}
return sv[i];
}
int maxVal(int n, int v) {
int res = n, remain = n;
for (auto x: val) {
int cur = remain - x;
remain -= cur;
if (x == v) {
continue;
}
res -= cur;
// cout << x << " " << remain << " " << res << "\n";
}
return res - used[v];
}
int find_best(int n) {
int pos = -1;
while (true) {
int opos = pos;
int l = pos + 1;
auto tmp = myAsk(l);
if (!tmp[0] && !tmp[1]) {
return l;
}
int r = l + maxVal(n, tmp[0] + tmp[1]) - 1;
set < int > :: iterator it = spos.lower_bound(l);
while (it != spos.end()) {
if (*it > r) {
break;
}
if (sv[*it] != tmp) {
r = *it - 1;
break;
}
it ++;
}
// cout << tmp[0] + tmp[1] << " " << l << " " << r << "\n";
while (l <= r) {
int mid = (l + r) >> 1;
auto cur = myAsk(mid);
if (!cur[0] && !cur[1]) {
return mid;
}
if (cur == tmp) {
pos = mid;
l = mid + 1;
}
else {
r = mid - 1;
}
}
used[tmp[0] + tmp[1]] += pos - opos;
}
}
