#include "secret.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
vector<int> a;
int n;
static int dp[5005][5005]; // use a bit larger static array
void build(int L, int R){
if(L == R){
dp[L][R] = a[L];
return;
}
int mid = (L + R) / 2;
// ensure dp[mid][mid] is set
dp[mid][mid] = a[mid];
// compute dp[i][mid] for i = mid-1 .. L (range i..mid)
for(int i = mid - 1; i >= L; --i){
// dp[i+1][mid] must already exist (we work leftwards)
dp[i][mid] = Secret(a[i], dp[i+1][mid]); // a[i] ★ (a[i+1]★...★a[mid])
}
// compute dp[mid][i] for i = mid+1 .. R (range mid..i)
for(int i = mid + 1; i <= R; ++i){
dp[mid][i] = Secret(dp[mid][i-1], a[i]); // (a[mid]★...★a[i-1]) ★ a[i]
}
// recurse
build(L, mid);
build(mid+1, R);
}
void Init(int N, int A[]){
n = N;
// initialize dp to a sentinel (here -1)
for(int i = 1; i <= n; ++i)
for(int j = 1; j <= n; ++j)
dp[i][j] = -1;
a.clear();
a.pb(0); // dummy so that a[1..n] exists
for(int i = 0; i < N; ++i) a.pb(A[i]);
build(1, n);
}
int Query(int L, int R){
// user supplies 0-based L,R; your code increments them to 1-based
++L; ++R;
if(L > R) return -1;
if(dp[L][R] != -1) return dp[L][R];
// try to find a split i in [L..R-1] such that dp[L][i] and dp[i+1][R] are known
for(int i = L; i <= R - 1; ++i){
if(dp[L][i] != -1 && dp[i+1][R] != -1){
return Secret(dp[L][i], dp[i+1][R]);
}
}
// should not happen if build fully covers needed ranges
return -1;
}
