#include "prize.h"
#include <bits/stdc++.h>
using namespace std;
int A[200009]; map<int, vector<int> >Map;
vector<int> asks(int pos) {
if (Map[pos].size() >= 1) return Map[pos];
Map[pos] = ask(pos);
return Map[pos];
}
vector<int> find_next(vector<int> R) {
int S = sqrt(R.size()) + 1;
int TT = 0, U = 1; while (U <= 1000) { U *= S; TT++; }
int maxn = 0;
for (int i = 0; i < TT; i++) {
vector<int> P = asks(R[rand() % R.size()]);
maxn = max(maxn, P[0] + P[1]);
}
int cx = 0; vector<int> T;
while (cx < (int)R.size()) {
vector<int> P = asks(R[cx]);
if (P[0] + P[1] != maxn) { T.push_back(R[cx]); cx++; continue; }
if (cx + 1 == (int)R.size()) break;
int B = 512;
if (R.size() <= 500) B = 32768;
int cl = 0, cr = min((int)R.size() - cx, B), cm, maxn = -1; bool flag = false;
while (true) {
bool terminate = false; if (cr - cl <= 1) terminate = true;
cm = (cl + cr) / 2;
//cout << "cx = " << cx << ", cl = " << cl << ", cr = " << cr << ", cm = " << cm << ", maxn = " << maxn << endl;
vector<int> Q = asks(R[cx + cm]);
if (P == Q) {
if (flag == true) cl = cm;
else cr *= 2;
if (flag == false && cr >= (int)R.size() - cx) { flag = true; cr = R.size() - cx; }
maxn = max(maxn, cx + cm);
}
else { cr = cm; flag = true; }
if (terminate == true) break;
}
if (maxn == (int)R.size() - 1) break;
T.push_back(R[maxn + 1]);
cx = maxn + 2;
}
//for (int i = 0; i < T.size(); i++) cout << T[i] << ", "; cout << endl;
return T;
}
int find_best(int n) {
vector<int> E; for (int i = 0; i < n; i++) E.push_back(i);
while (E.size() >= 2) E = find_next(E);
return E[0];
}
