#include "prize.h"
#include <bits/stdc++.h>
using namespace std;
#define REP(a,b,c) for(int a=int(b); a<int(c); a++)
#define REV(a,b,c) for(int a=int(c-1); a>=int(b); a--)
#define RE(a,b) REP(a,0,b)
#define FOR(a,b) for(auto& a:b)
#define pb push_back
#define fi first
#define se second
#define all(a) a.begin(), a.end()
typedef long long ll;
typedef pair<int,int> ii;
typedef vector<int> vi;
typedef vector<ii> vii;
const int INF=1e9;
const int MX=1e5;
map<int, vi> mem;
map<int, map<int, int>> bst;
vi Ask(int i) {
if(mem.count(i)) return mem[i];
vi ret = ask(i);
int sm = ret[0]+ret[1];
if(!bst[sm].count(ret[0])) bst[sm][ret[0]] = i;
bst[sm][ret[0]] = min(bst[sm][ret[0]], i);
return mem[i] = ret;
}
int find_best(vi f) {
int n = f.size();
if(n == 1) return f[0];
int sq = ceil(sqrt(n))+1;
int mn = min(sq*2, n);
int sm = 0;
RE(i,mn) {
vi res = Ask(f[i]);
sm = max(sm, res[0]+res[1]);
}
vi g;
RE(i,sm) {
int lb=0, ub=n-1;
while(lb != ub) {
int mid=(lb+ub+1)/2;
vi res = Ask(f[mid]);
if(res[0] + res[1] == sm) {
if(res[0] > i) ub=mid-1;
else lb=mid+1;
} else {
int j = mid;
while(1) {
j--;
if(j == -1) {
lb = ub = 0;
break;
}
res = Ask(f[j]);
if(res[0] + res[1] == sm) {
if(res[0] == i) {
lb = ub = j+1;
}
break;
}
}
if(lb == ub) {
REP(k,lb,mid+1) {
g.pb(f[k]);
}
i += mid-lb;
break;
} else {
res = Ask(f[j]);
if(res[0] > i) ub=j-1;
else lb=j+1;
}
}
}
}
return find_best(g);
}
int find_best(int n) {
vi f;
RE(i,n) f.pb(i);
return find_best(f);
}
