#include "prize.h"
#include <bits/stdc++.h>
#define fi first
#define se second
#define ryan bear
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef long double ld;
typedef vector<int> vim;
int N;
set<pair<int, pii> > S[10]; int val[10], tp;
int ans, fl, chk[200010], ar[200010];
int f(int v) {
for (int i=0; i<tp; i++) if (val[i]==v) return i;
val[tp]=v; return tp++;
}
void myfind(int s, int e) {
if (s>e) return ;
int md=(s+e)/2;
if (chk[md]) return ;
chk[md]=1;
vim res=ask(md);
ar[md]=res[0]+res[1];
if (res[0]==0&&res[1]==0) {
ans=md;
fl=1;
return ;
}
int ind=f(ar[md]);
S[ind].insert({md, make_pair(res[0], res[1])});
auto it=S[ind].find({md, make_pair(res[0], res[1])});
pair<int, pii> p=(*it), pr, ne;
if (it==S[ind].begin()) pr={-1, make_pair(0, ar[md])};
else pr=*prev(it);
if (next(it)==S[ind].end()) ne={N, make_pair(ar[md], 0)};
else ne=*next(it);
if (pr.se.fi!=p.se.fi) myfind(pr.fi+1, p.fi-1);
if (fl) return ;
if (p.se.fi!=ne.se.fi) myfind(p.fi+1, ne.fi-1);
}
int find_best(int n) {
N=n;
myfind(0, n-1);
if (!fl) assert(false);
return ans;
}
