#include "prize.h"
#include <bits/stdc++.h>
#define ii pair<int, int>
#define fi first
#define se second
#define inf 0x3f3f3f3f3f3f3f3f
using namespace std;
using ll = long long;
const ll mod=1e9+7;
const int nx=2e5+5;
int base;
// vector<int> ask(int i)
// {
// }
int solve(int l, int r, int cnt, int le, int ri)
{
if(l>r || !cnt) return -1;
int mid=(l+r)>>1;
vector<int> tmp=ask(mid);
if(tmp[0]+tmp[1]==0) return mid;
return max(solve(l, mid-1, cnt-(tmp[1]-ri), le, tmp[1]), solve(mid+1, r, cnt-(tmp[0]-le), tmp[0], ri));
}
int find_best(int n)
{
base=0;
for(int i = 0; i < min(500, n); i++)
{
vector<int> tmp=ask(i);
base=max(base, tmp[0]+tmp[1]);
if(base>=50) break;
}
return solve(0, n-1, base, 0, 0);
}
