#include "prize.h"
#include <bits/stdc++.h>
using namespace std;
const int MX = 1e6 + 66;
vector<int> memo[MX];
vector<int> query (int x) {
if (memo[x].size() == 0) {
memo[x] = ask(x);
}
return memo[x];
}
mt19937 rng(time(NULL));
int find_best (int N) {
int node = rng() % N;
query(node);
for (int i = 0;i < 3;i ++) {
int node2 = rng() % N;
query(node2);
if (memo[node][0] + memo[node][1] < memo[node2][0] + memo[node2][1]) node = node2;
}
// cerr << node << "\n";
int low = 0, high = node;
for (int i = memo[node][0] - 1;i >= 0;i --) {
while (low < high) {
int mid = (low + high + 1) / 2;
query(mid);
if (memo[mid][0] + memo[mid][1] == memo[node][0] + memo[node][1]) {
if (memo[mid][0] >= i) high = mid - 1;
else low = mid + 1;
} else {
low = mid;
}
}
// cerr << high << "\n";
query(high);
assert(memo[high][0] + memo[high][1] < memo[node][0] + memo[node][1]);
if (memo[high][0] + memo[high][1] == 0) return high;
low = 0;
}
low = node;
high = N - 1;
for (int i = memo[node][0];i < memo[node][0] + memo[node][1];i ++) {
while (low < high) {
int mid = (low + high) / 2;
query(mid);
if (memo[mid][0] + memo[mid][1] == memo[node][0] + memo[node][1]) {
if (memo[mid][0] <= i) low = mid + 1;
else high = mid - 1;
} else {
high = mid;
}
}
// cerr << high << "\n";
query(high);
assert(memo[high][0] + memo[high][1] < memo[node][0] + memo[node][1]);
if (memo[high][0] + memo[high][1] == 0) return high;
high = N - 1;
}
return -2;
}
