#include "prize.h"
#include "bits/stdc++.h"
using namespace std;
#define ll long long
#define rep(i, n) for(int i = 1; i <= (n); ++i)
#define REP(i, n) for(int i = 0; i < (n); ++i)
#define forn(i, l, r) for(int i = (l); (i) <= (r); ++i)
#define ford(i, r, l) for(int i = (r); (i) >= (l); --i)
#define endl "\n"
#define fi first
#define se second
#define pb push_back
#define pll pair<ll, ll>
#define pii pair<int, int>
#define all(a) a.begin(), a.end()
#define sz(a) (int)(a.size())
#define task "note"
template<typename T> bool maximize(T &res, const T &val) {if(res < val) {res = val; return 1;} return 0;}
template<typename T> bool minimize(T &res, const T &val) {if(res < val) return 0; res = val; return 1;}
inline int readInt() {char c;while(c=getchar(),c!='-'&&(c<'0'||c>'9'));bool sign=(c=='-');if(sign)c=getchar();int n=c-'0';while(c=getchar(),c>='0'&&c<='9')n=10*n+c-'0';return(!sign)?n:-n;}
inline ll readLong() {char c;while(c=getchar(),c!='-'&&(c<'0'||c>'9'));bool sign=(c=='-');if(sign)c=getchar();ll n=c-'0';while(c=getchar(),c>='0'&&c<='9')n=10*n+c-'0';return(!sign)?n:-n;}
inline string readString() {char c;while(c=getchar(),c==' '||c=='\n'||c=='\t');string s({c});while(c=getchar(),c!=EOF&&c!=' '&&c!='\n'&&c!='\t')s+=c;return s;}
const int N = 2e5 + 3;
const int LOG = 12;
const int INF = 2e9;
const int S = 450;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
double get_cur_time() {return chrono::steady_clock::now().time_since_epoch().count();}
int n;
bool used[N];
pii dat[N];
int ans;
int num = 0;
pii get(int x)
{
if(used[x]) return dat[x];
vector<int> tmp = ask(x);
used[x] = 1;
dat[x] = {tmp[0], tmp[1]};
if(tmp[0] + tmp[1] == 0) ans = x;
return dat[x];
}
int num_iter = 0;
void dnc_pre(int l, int r)
{
if(l > r) return;
int mid = l + r >> 1;
pii x = get(mid);
maximize(num, x.fi + x.se);
dnc_pre(l, mid - 1);
dnc_pre(mid + 1, r);
}
void dnc_calc(int l, int r, int num_l, int num_in)
{
if(num_in == 0) return;
if(l > r) return;
int mid = l + r >> 1;
int new_num = 0;
for(int i = mid; i >= l; --i)
{
pii x = get(i);
if(x.fi + x.se == num)
{
new_num += x.fi - num_l;
break;
}
++new_num;
}
dnc_calc(l, mid - 1, num_l, new_num);
dnc_calc(mid + 1, r, num_l + new_num, num_in - new_num);
}
int find_best(int N)
{
n = N;
dnc_pre(0, n - 1);
dnc_calc(0, n - 1, 0, num);
return ans;
}
