#include "prize.h"
#include <bits/stdc++.h>
using namespace std;
int nbPrix;
vector<int> perm;
vector<int> rv[200*1005];
int outil = -1;
vector<int> realGet(int x)
{
vector<int> &res = rv[x];
if (res.empty()) res = ask(x);
return res;
}
#define ask flrfldl
int rp=-1;
void trouver(int a, int b, int va, int vb)
{
if (a+1 >= b) return;
va = a; vb = b;
int mid = (va + vb) / 2;
int niceSp = -1;
for (int split = mid; split < b; ++split) {
auto res = realGet(split);
int val = res[0] + res[1];
if (val == 0) { rp = split; return; }
if (val == outil) { niceSp = split; break; }
}
if (niceSp == -1) {
for (int split = mid; split > a; --split) {
auto res = realGet(split);
int val = res[0] + res[1];
if (val == 0) { rp = split; return; }
if (val == outil) { niceSp = split; break; }
}
}
if (niceSp != -1) {
if (realGet(a)[0] != realGet(niceSp)[0]) {
trouver(a, niceSp, a, min(mid, niceSp));
if (rp != -1) return;
}
if (realGet(niceSp)[1] != realGet(b)[1]) {
trouver(niceSp, b, max(mid, niceSp), b);
}
}
}
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(477, nbPrix);
int lolId=-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;
}
if (val > 40) break;
}
int der = n-1;
while (true) {
auto res = realGet(der);
int val = res[0] + res[1];
if (val == 0) return der;
if (val == outil) break;
--der;
}
trouver(lolId, der, lolId, der);
return rp;
}
