#include "prize.h"
#include <bits/stdc++.h>
using namespace std;
// macros
typedef long long ll;
typedef long double ld;
typedef pair<int, int> ii;
typedef pair<ll, ll> lll;
typedef tuple<int, int, int> iii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<iii> viii;
typedef vector<ll> vll;
typedef vector<lll> vlll;
#define REP(a,b,c) for(int a=int(b); a<int(c); a++)
#define RE(a,c) REP(a,0,c)
#define RE1(a,c) REP(a,1,c+1)
#define REI(a,b,c) REP(a,b,c+1)
#define REV(a,b,c) for(int a=int(c-1); a>=int(b); a--)
#define FOR(a,b) for(auto& a : b)
#define all(a) a.begin(), a.end()
#define INF 1e9
#define EPS 1e-9
#define pb push_back
#define popb pop_back
#define fi first
#define se second
#define sz size()
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
int big=0;
int n;
vi Ask(int i) {
static map<int,vi> mem;
auto it = mem.find(i);
if(it != mem.end())
return it->second;
return mem[i] = ask(i);
}
int getSum(int i) {
if(i < 0 || i >= n) return big;
return Ask(i)[0] + Ask(i)[1];
}
int getBiggestSize() {
int res = 0;
RE(i,448)
res = max(res, getSum(i));
return res;
}
int getIndex(int i) {
int lb=0, ub=n-1;
while(lb < ub) {
int mid=(lb+ub)/2;
int sm = getSum(mid);
int len = 0;
if(sm != big) {
while(sm != big) sm = getSum(++mid);
sm = getSum(--mid);
while(sm != big) sm = getSum(--mid), len++;
int res = mid == -1 ? 0 : Ask(mid)[0];
if(i >= res && i < res+len)
return mid + 1 + i - res;
if(res > i) ub = mid-1;
else lb = mid+len+1;
continue;
}
int res = Ask(mid)[0];
if(res > i) ub = mid-1;
else lb = mid+1;
}
return lb;
}
int find_best(int N) {
n = N;
if(n <= 5000) {
RE(i,n) {
int res = getSum(i);
if(res == 0)
return i;
}
}
big = getBiggestSize();
RE(i,big) {
int j = getIndex(i);
if(getSum(j) == 0)
return j;
}
return -1;
}
