#include <bits/stdc++.h>
#include "prize.h"
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
template<typename K>
using ordered_set = tree
<K, null_type, less<K>,
rb_tree_tag,
tree_order_statistics_node_update
>;
int answer = -1;
int mx_cnt = 0;
ordered_set<int> found;
map<int, array<int, 2>> memo;
int found_in_range(int l, int r) {
return found.order_of_key(r) - found.order_of_key(l);
}
array<int, 2> askme(int i) {
array<int, 2> ans;
if (memo.find(i) != memo.end()) {
ans[0] = memo[i][0];
ans[1] = memo[i][1];
} else {
auto v = ask(i);
ans[0] = v[0];
ans[1] = v[1];
}
memo[i] = {ans[0], ans[1]};
if (ans[0] + ans[1] != mx_cnt) found.insert(i);
if (ans[0] + ans[1] == 0) answer = i;
return ans;
}
inline int count(int i) { return askme(i)[0] + askme(i)[1]; }
void findall(int l, int r) {
// assume t[l] = t[r] = v
int cnt = askme(r)[0] - askme(l)[0];
if (cnt <= found_in_range(l, r)) return;
if (answer != -1) return;
int m = (l + r) / 2;
int lm = m, rm = m;
while (count(lm) < count(l)) {
if (answer != -1) return;
--lm;
}
while (count(rm) != count(l)) {
if (answer != -1) return;
++rm;
}
findall(l, lm);
findall(rm, r);
}
int find_best(int n) {
#ifndef LORENZO
if (n <= 5000) {
for (int i = 0; i < n; ++i) ask(i);
return answer;
}
#endif
srand(time(NULL));
for (int i = 0; i < 450; ++i) mx_cnt = max(mx_cnt, count(i));
int l = 0; while (count(l) != mx_cnt) ++l;
int r = n-1; while (count(r) != mx_cnt) --r;
findall(l, r);
return answer;
}
#ifdef LORENZO
int main() {
cout << "insert n: "; fflush(stdout);
int n; cin >> n;
cout << "answer: " << find_best(n) << endl;
}
#endif
