#include "prize.h"
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 2e5 + 5;
vector<vector<int>> dp(MAX_N);
map<int, set<int> > memo[MAX_N];
set<int> query;
int find_best(int n) {
pair<int, int> best_way = {-1, -1};
auto perguntar = [&](int delta) {
//~ if (dp[delta].empty()) {
//~ dp[delta] = ask(delta);
//~ }
vector<int> res = ask(delta); // dp[delta];
//~ memo[dp[delta][0]][dp[delta][1]].insert(delta);
//~ query.insert(delta);
return make_pair(res[0], res[1]);
};
auto calc_score = [&](const pair<int, int> &res) {
return res.first + res.second;
};
//~ auto find = [&](const pair<int, int> &res) {
//~ const int l = res.first;
//~ const int r = res.second;
//~ if (memo[l][r].empty()) return -1;
//~ return *memo[l][r].rbegin();
//~ };
//~ auto rightmost = [&](int idx) -> int {
//~ ++idx;
//~ auto where = query.lower_bound(idx);
//~ if (where == query.end()) return 1e9;
//~ return *where;
//~ };
for (int i = 0; i < min(n, 1000); i++) {
pair<int, int> res = perguntar(i);
best_way = max(best_way, {calc_score(res), i});
if (calc_score(res) == 0) {
//~ return i;
}
}
int idx = best_way.second;
while(idx < n) {
pair<int, int> res = perguntar(idx);
//~ cout << res.first << ' ' << res.second << '\n';
//~ cout << perguntar(best_way.second).first << ' ' << perguntar(best_way.second).second << '\n';
if (res == perguntar(best_way.second)) {
int l = idx;
int r = n - 1;
while(l < r) {
const int mid = l + (r - l) / 2 + 1;
pair<int, int> cur = perguntar(mid);
//~ if (calc_score(cur) == 0) {
//~ return mid;
//~ }
if (res == cur) {
l = mid;
} else {
r = mid - 1;
}
}
idx = l + 1;
} else {
if (calc_score(res) == 0) {
//~ return idx;
}
++idx;
}
}
assert(1 == 2);
}
