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