#include "prize.h"
#include <bits/stdc++.h>
using namespace std;
int MAX = 500;
map<int, vector<int>> memo;
vector<int> qry(int i){
if(memo.count(i)) return memo[i];
vector<int> a = ask(i);
return memo[i] = a;
}
int find_best(int n) {
MAX = min(n, MAX);
int v = 0;
for(int i = 0; i < MAX; i++){
vector<int> a = qry(i);
if(a[0] + a[1] == 0) return i;
v = max(v, a[0]+a[1]);
}
vector<int> pos;
for(int i = MAX; i < n; i++) pos.push_back(i);
vector<pair<int, int>> found;
for(int i = 0; i < MAX; i++){
vector<int> a = qry(i);
if(a[0] + a[1] < v) found.emplace_back(i, a[0]+a[1]);
}
while(true){
int lo = 0, hi = (int)pos.size()-1;
for(int mid = (lo+hi)/2; lo <= hi; mid=(lo+hi)/2){
int p = pos[mid];
vector<int> a = qry(p);
if(a[0]+a[1] == 0) return p;
if(a[0]+a[1] != v){
found.emplace_back(p, a[0]+a[1]);
pos.erase(pos.begin()+mid);
break;
}
int cnt = 0;
for(auto [i, x] : found){
if(i < p && x < v) cnt++;
}
if(cnt < a[0]) hi = mid-1;
else lo = mid+1;
}
}
return -1;
}
