#include "prize.h"
#include <bits/stdc++.h>
using namespace std;
int nbPrix;
vector<int> perm;
vector<int> rv[200*1005];
vector<int> realGet(int x)
{
vector<int> &res = rv[x];
if (res.empty()) res = ask(x);
return res;
}
#define ask flrfldl
int find_best(int n)
{
nbPrix = n;
if (nbPrix <= 5000) {
for (int i = 0; i < nbPrix; ++i) {
auto res = realGet(i);
if (res[0] + res[1] == 0) return i;
}
}
int lim = min(500, nbPrix);
int lolId=-1, outil=-1;
for (int pos = 0; pos < lim; ++pos) {
auto res = realGet(pos);
int val = res[0] + res[1];
if (val > outil) {
lolId = pos;
outil = val;
}
if (val == 0) {
return pos;
}
}
while (true) {
int curLeft = realGet(lolId)[0];
int lo = lolId, ri = nbPrix-1;
assert(realGet(nbPrix-1)[0] != curLeft);
while (lo < ri) {
int mid = (lo+ri) / 2;
int valMid = realGet(mid)[0];
int valTot = valMid + realGet(mid)[1];
if (valTot != outil || valMid != curLeft) ri = mid;
else lo = mid+1;
}
int curPos = lo;
while (true) {
auto res = realGet(curPos);
int val = res[0] + res[1];
if (val == 0) return curPos;
if (val == outil) {
lolId = curPos;
break;
}
++curPos;
}
}
}
