#include <bits/stdc++.h>
#include "prize.h"
#define F first
#define S second
#define pii pair<int, int>
#define pb push_back
using namespace std;
typedef long long ll;
const int maxN = 480;
int p = -1, ted;
void solve(int l, int r, int k, int kl, int kr)
{
if(r - l <= 0) return ;
if(k == 0) return ;
if(p != -1) return ;
if(r - l < 2)
{
if(l < maxN) return ;
vector <int> t = ask(l);
if(t[0] + t[1] == 0) p = l;
return ;
}
int mid = (l + r)/2;
int i = mid, cnt = 0;
bool ok = false;
while(i < r)
{
vector <int> t = ask(i);
if(t[0] + t[1] < ted){
if(t[0] + t[1] == 0) p = i;
i ++;
cnt ++;
}else
{
int a = t[0], b = t[1];
a -= kl; a -= cnt;
solve(l, mid, a, kl, cnt + t[1]);
solve(i + 1, r, b - kr, t[0], kr);
ok = true;
break ;
}
}
if(ok) return ;
solve(l, mid, k - cnt, kl, cnt + kr);
return ;
}
int find_best(int n) {
for(int i = 0; i < min(maxN, n); i++) {
vector<int> res = ask(i);
if(res[0] + res[1] == 0)
return i;
ted = max(ted, res[0] + res[1]);
}
solve(0, n, ted, 0, 0);
return p;
}
