#include "prize.h"
#include <bits/stdc++.h>
#define x first
#define y second
using namespace std;
const int INF = 1e9;
typedef long long ll;
typedef pair <int,int> pi;
typedef vector <int> vec;
using namespace std;
vector <int> g[435];
int di = 473,m,n,pmx,la,big;
vec d[200005];
vec getAsk(int x) {
if(d[x][0] != -1) return d[x];
return d[x] = ask(x);
}
int find_best(int N) {
n = N; m = n/di+(n%di>0);
for(int i = 0;i < n;i++) d[i].push_back(-1), d[i].push_back(-1);
for(int i = 0;i < m;i++) {
for(int j = i*di;j < min(n,i*di+di);j++) g[i].push_back(j);
}
int cn = 0;
for(int i = 0;i < m&&cn < di;i++,cn++) {
vec tmp = getAsk(g[i].back());
pmx = max(pmx,tmp[0]+tmp[1]);
}
for(int i = 0;i < n&&cn < di;i++,cn++) {
vec tmp = getAsk(i);
pmx = max(pmx,tmp[0]+tmp[1]);
}
la = -1;
for(int i = 0;i < m;) {
//cout << i << ' ' << la << '\n';
vec tmp = getAsk(g[i].back());
if(la == g[i].back()) {
i++; continue;
}
if(tmp[0]+tmp[1] == pmx&&tmp[0] == big) {
i++; continue;
}
la = max(la+1,g[i][0]);
int l = la,r = g[i].back();
int wi = -1;
while(l <= r) {
int mid = (l + r) >> 1;
vec t = getAsk(mid);
if(t[0]+t[1] != pmx) wi = mid;
if(t[0]+t[1] != pmx||t[0] != big) r = mid-1;
else l = mid+1;
}
if(wi == -1) while(1);
vec t2 = getAsk(wi);
if(t2[0]+t2[1] == pmx) while(1);
if(t2[0]+t2[1] == 0) return wi;
la = wi;
big++;
}
return -1;
}
