# include <iostream>
# include <vector>
# include <cassert>
# include <map>
using namespace std;
# include "prize.h"
//# include "grader.cpp"
int n;
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;
}
}
}
int find_best(int N)
{
n=N;
for(long long i=1;i<=n;i++)
{
if(i*i>=n)
{
s=i;
break;
}
}
s=450;
for(int i=0;i<min(s,n);i++)
{
pair<int,int> pa=query(i);
int sum=pa.first+pa.second;
if(big<sum) big=sum;
}
int l=n-1,r=0;
for(int i=0;i<n;i++)
{
if(large(i))
{
l=i;
break;
}
}
for(int i=n-1;i>=0;i--)
{
if(large(i))
{
r=i;
break;
}
}
rec(l,r);
for(auto P: Data)
{
int id=P.first;
int sum=P.second.first+P.second.second;
if(sum==0) return id;
}
assert(0);
return -1;
}
/*
8
3 2 3 1 3 3 2 3
*/
/*
8
2 1 2 2 2 2 2 2 2
*/
