#include <bits/stdc++.h>
#include "secret.h"
using namespace std;
const int mxN = 1005;
int a[mxN], dp[mxN][mxN], n;
unordered_map<int, unordered_map<int, int>> mp;
int token = 0;
int get(int x, int y){
if(x == -1) return y;
if(y == -1) return x;
if(mp.count(x)){
if(mp[x].count(y)){
return mp[x][y];
}
}
token += 1;
return mp[x][y] = Secret(x, y);
}
int solve(int l, int r){
if(l > r) return -1;
if(dp[l][r] != -1) return dp[l][r];
if(l + 1 == r) return dp[l][r] = get(a[l], a[r]);
int mid = (l + r) / 2;
int left = solve(l, mid), right = solve(mid + 1, r);
return dp[l][r] = get(left, right);
}
int get_token(int l, int r){
if(l > r) return 0;
if(dp[l][r] != -1) return 0;
if(l + 1 == r) return 1;
int mid = (l + r) / 2;
int left = get_token(l, mid), right = get_token(mid + 1, r);
return left + right;
}
void Init(int N, int A[]) {
memset(dp, -1, sizeof(dp));
n = N;
for(int i = 0; i < N; ++i){
a[i] = A[i];
dp[i][i] = A[i];
}
for(int len = 2; len <= n; ++len){
bool work = 1;
for(int i = 0; i < n; ++i){
int j = i + len - 1;
if(j < n){
int current_token = get_token(i, j) + 1;
if((current_token + token) > 8000){
work = 0;
break;
}
solve(i, j);
}
}
if(!work) break;
}
}
int Query(int L, int R) {
return solve(L, R);
}
