# include <iostream>
# include <vector>
# include <cassert>
# include <map>
using namespace std;
# include "prize.h"
//# include "grader.cpp"
int n;
int S=400;
int getB(int x) {return x/S;}
int getL(int x) {return x*S;}
int getR(int x) {return min(n,(x+1)*S-1);}
map<int,pair<int,int>> Data;
pair<int,int> query(int i)
{
if(Data.find(i)==Data.end())
{
vector<int> arr=ask(i);
Data[i]={arr[0],arr[1]};
}
return Data[i];
}
int s,big;
bool large(int i)
{
pair<int,int> pa=query(i);
long long sum=pa.first+pa.second;
return sum==big;
}
void rec(int l, int r)
{
//cout<<l<<" "<<r<<"\n";
if(l==r) return ;
pair<int,int> L=query(l),R=query(r);
if(L.second==R.second or L.first==R.first) return ;
int mid=(l+r)/2;
for(int i=mid;i>=l;i--)
{
if(large(i))
{
rec(l,i);
break;
}
}
for(int i=mid+1;i<=r;i++)
{
if(large(i))
{
rec(i,r);
break;
}
}
}
void solve(int l, int r)
{
int L=-1,R=-1;
for(int i=l;i<=r;i++)
{
if(large(i))
{
L=i;
break;
}
}
for(int i=r;i>=l;i--)
{
if(large(i))
{
R=i;
break;
}
}
if(L!=-1)
{
rec(L,R);
}
}
int find_best(int N)
{
n=N;
if(n<500)
{
for(int i=0;i<n;i++)
{
pair<int,int> pa=query(i);
if(pa.first+pa.second==0) return i;
}
return -1;
}
S=n/500;
int bl=getB(n-1);
for(int i=0;i<=bl;i++)
{
pair<int,int> pa=query(getL(i));
if(pa.first+pa.second<big) big=pa.first+pa.second;
}
for(int i=0;i<=bl;i++)
{
solve(getL(i),getR(i));
}
for(auto P: Data)
{
int id=P.first;
int sum=P.second.first+P.second.second;
if(sum==0) return id;
}
return -1;
}
/*
8
3 2 3 1 3 3 2 3
*/
/*
8
2 1 2 2 2 2 2 2 2
*/
