#include "prize.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define rep(a, b) for(int a = 0; a < (b); ++a)
#define st first
#define nd second
#define pb push_back
#define all(a) a.begin(), a.end()
const int LIM=2e5+7;
int tr[4*LIM], ile, N=1;
int T[LIM][2], wynik=-1;
void pytaj(int x) {
if(T[x][0]!=-1) return;
vector<int>V=ask(x);
T[x][0]=V[0];
T[x][1]=V[1];
if(T[x][0]+T[x][1]==0) wynik=x;
}
void upd(int v) {
v+=N;
tr[v]=1;
v/=2;
while(v) {
tr[v]=tr[2*v]+tr[2*v+1];
v/=2;
}
}
int cnt(int v) {
v+=N;
int ans=tr[v];
while(v>1) {
if(v%2==1) ans+=tr[v-1];
v/=2;
}
return ans;
}
void pytaj2(int x) {
pytaj(x);
if(T[x][0]+T[x][1]<ile) upd(x);
}
void solve(int l, int r, int k) {
if(l>r) return;
if(cnt(r)==k) return;
if(l==r) {
pytaj2(l);
return;
}
int mid=(l+r)/2;
pytaj2(mid);
while(T[mid][0]+T[mid][1]<ile && mid<r) {
++mid;
pytaj2(mid);
}
if(T[mid][0]+T[mid][1]==ile) {
solve(l, mid-1, T[mid][0]);
solve(mid+1, r, k);
} else {
mid=(l+r)/2;
while(T[mid][0]+T[mid][1]<ile && mid>l) {
--mid;
pytaj2(mid);
}
if(T[mid][0]+T[mid][1]==ile) {
solve(l, mid-1, T[mid][0]);
}
}
}
int find_best(int n) {
rep(i, n) T[i][0]=-1;
if(n<=5000) {
rep(i, n) pytaj(i);
return wynik;
}
while(N<n) N*=2;
int p=n/450;
for(int i=p; i<n; i+=p) {
pytaj(i);
ile=max(ile, T[i][0]+T[i][1]);
}
rep(i, n) if(T[i][0]!=-1) pytaj2(i);
int x=p;
while(T[x][0]+T[x][1]<ile && x>0) {
--x;
pytaj2(x);
}
if(T[x][0]+T[x][1]<ile) upd(x);
if(x>0) solve(0, x-1, T[x][0]);
for(int i=p; i+p<n; i+=p) {
x=i;
while(T[x][0]+T[x][1]<ile && x<i+p) {
++x;
pytaj2(x);
}
int y=min(i+p, n-1);
pytaj2(y);
while(T[y][0]+T[y][1]<ile && y>x) {
--y;
pytaj2(y);
}
if(x+1<=y-1) solve(x+1, y-1, T[y][0]);
}
return wynik;
}
