#include "prize.h"
#include <bits/stdc++.h>
using namespace std;
//#define int long long
typedef pair<int,int> pii;
typedef vector<int> vi;
#define fi first
#define se second
#define debug(x) cerr<<#x<<" is "<<x<<endl;
#define sz(x) (int)(x).size()
#define pb push_back
#define ipii pair<int,pii>
const int inf=1e9+5;
int ans=-1;
int nn;
int cnt;
map<int,set<ipii>> s;
void check(int l,int h){
//debug(l)debug(h)
if(ans!=-1)return;
bool f=1;
if(l==h-1)return;
int m=(l+h)/2;
vi res=ask(m);
cnt++;
assert(cnt<=10000);
//debug(m)debug(res[0])debug(res[1])
int tt=res[0]+res[1];
if(tt==0)ans=m;
//if(s[tt].empty())s[tt].insert({-1,{0,0}});
s[tt].insert({m,{res[0],res[1]}});
auto it=s[tt].lower_bound({m,{0,0}});
auto it2=s[tt].upper_bound({h,{inf,inf}});
if( !((it2!=s[tt].end()&&(*it2).se.fi==res[0])))check(m,h);
it=s[tt].lower_bound({l,{0,0}});
if( !((it!=s[tt].begin()&&(*--it).se.fi==res[0])))check(l,m);
}
int find_best(int n) {
nn=n;
check(-1,n);
//nn=n;
//for(int i=0;i<30000;i++)ask(0);
return ans;
}
