#include <bits/stdc++.h>
#include "prize.h"
using namespace std;
int mn = INT_MAX;
int le = 0, ri;
int s(int l, int r) {
if(l < le || r > ri) {
if(max(l, le) > min(r, ri))
return -1;
return s(max(l, le), min(r, ri));
}
int mid = (l+r)/2;
vector<int>gt = ask(mid);
if(gt[0]+gt[1] <= mn) {
mn = gt[0]+gt[1];
if(gt[0] == 0)
le = max(le, mid+1);
if(!gt[1])
ri = min(ri, mid-1);
}
if(!gt[0] && !gt[1])
return mid;
if(l == r)
return -1;
int a = -1, b = -1;
if(gt[0] && l < mid)
a = s(l, mid-1);
if(gt[1] && r > mid)
b = s(mid+1, r);
return max(a,b);
}
int find_best(int n) {
ri = n-1;
return s(0,n-1);
}
