#include "prize.h"
#include <bits/stdc++.h>
using namespace std;
vector<int> ask(int i);
int find_best(int n) {
int ans = -1;
int rejectedright = n,rejectedleft = -1;
queue<pair<int,int>>q;
q.push({0,n - 1});
map<int,set<pair<int,int>>>pq;
while(!q.empty()){
auto u = q.front();
q.pop();
int left = u.first,right = u.second;
if (left > right)continue;
if (left >=rejectedright)continue;
if (right<=rejectedleft)continue;
if (right > rejectedright){
q.push({left,rejectedright - 1});
continue;
}
if (left < rejectedleft){
q.push({rejectedleft + 1,right});
continue;
}
if (left == right){
vector<int>res = ask(left);
pq[res[0] + res[1]].insert(make_pair(left,res[1]));
if (res[0] + res[1] == 0){
ans = left;
break;
}
continue;
}
int mid = (left + right)>>1;
vector<int>res = ask(mid);
pq[res[0] + res[1]].insert(make_pair(mid,res[1]));
if (res[0] + res[1] == 0){
ans = mid;
break;
}
auto it = pq[res[0] + res[1]].find(make_pair(mid,res[1]));
if (res[0] > 0){
bool ok = true;
if (it != pq[res[0] + res[1]].begin()){
auto it2 = *prev(it);
if (it2.second - res[1] <=0)ok = false;
}
if (ok){
q.push({left,mid - 1});
}
else{
//rejectedleft = max(rejectedleft,mid);
}
}
else{
rejectedleft = max(rejectedleft,mid);
}
if (res[1] > 0){
bool ok = true;
if (next(it)!=pq[res[0] + res[1]].end()){
auto it2 = *next(it);
if (res[1] - it2.second <=0)ok = false;
}
if (ok){
q.push({mid + 1,right});
}
else{
//rejectedright = min(rejectedright,mid);
}
}
else{
rejectedright = min(rejectedright,mid);
}
}
return ans;
}
