#include <bits/stdc++.h>
#define pb push_back
#include "prize.h"
using namespace std;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
int rnd(int B) {
int y = rng();
y = abs(y);
return y % B;
}
bool fix[200003];
int Q;
vector <int> dp[200003];
vector <int> askk(int x){
if (dp[x].size()) return dp[x];
++Q;
// if (Q > 10000) assert(0);
return dp[x] = ask(x);
}
int find_best(int n){
int block = sqrt(n) + 1;
int mxx=-1;
while (1){
vector <int> v;
for (int j=0;j<n;j++){
if (!fix[j]) v.pb(j);
}
int mx = -1,id = -1;
vector <int> opt;
int len = (int)v.size();
for (int i = 0; i < min(len,block); i++){
int x = v[i];
vector <int> vec = askk(x);
int sum = vec[0] + vec[1];
if (sum == 0) return x;
if (sum > mx){
mx = sum;
id = x;
opt = vec;
}
}
// if (len < block) assert(0);
if (mxx != -1 && mx != mxx) assert(0);
mxx=mx;
int l = id + 1,r = n - 1,res = id;
for (int i = id + 1; i < n; i++){
if (fix[i]){
r = i - 1;
break;
}
}
while (l <= r){
int mid = (l + r) >> 1;
vector <int> k = askk(mid);
if (k[0] + k[1] == 0) return mid;
if (k != opt){
r = mid - 1;
}else{
res = mid;
l = mid + 1;
}
}
// cout<<id<<" -> "<<res<<endl;
for (int i = id; i <= res; i++)
fix[i] = 1;
}
}
