#include "prize.h"
#include<bits/stdc++.h>
using namespace std;
#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;
vector<int>P[LIM];
int odw[LIM], ma, n;
void pytaj(int x) {
if(odw[x]) return;
odw[x]=1;
P[x]=ask(x);
ma=max(ma, P[x][0]+P[x][1]);
}
bool dobry(int x) {
if(x<0 || x>=n) return false;
pytaj(x);
return P[x][0]+P[x][1]<ma;
}
bool wygrany(int x) {
if(x<0 || x>=n) return false;
pytaj(x);
return P[x][0]+P[x][1]==0;
}
int solve(int l, int r) {
if(l>r) return -1;
if(wygrany(l-1)) return l-1;
if(dobry(l-1)) return solve(l+1, r);
if(wygrany(r+1)) return r+1;
if(dobry(r+1)) return solve(l, r-1);
int a=ma;
if(l) a=P[l-1][1];
if(r<n-1) a-=P[r+1][1];
if(!a) return -1;
int mid=(l+r)/2;
if(wygrany(mid)) return mid;
int p=solve(l, mid-1);
if(p!=-1) return p;
return solve(mid+1, r);
}
int find_best(int N) {
n=N;
if(n<=5000) {
rep(i, n) {
pytaj(i);
if(P[i][0]+P[i][1]==0) return i;
}
}
int x=n/500;
rep(i, 499) if(wygrany(x*(i+1))) return x*(i+1);
int p=solve(0, x-1);
if(p!=-1) return p;
rep(i, 498) {
p=solve(x*(i+1)+1, x*(i+2)-1);
if(p!=-1) return p;
}
return solve(x*499+1, n-1);
}
