#include "secret.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll MAXN = 1e3 + 5, inf = 1e9, mod = 1e9 + 7, block = 320, lim = 16;
int a[MAXN];
int n;
int dp[MAXN][MAXN];
void dnc(int l, int r) {
if (l > r) return;
if (l == r) {
dp[l][l] = a[l];
return;
}
int mid = (l + r) / 2;
dp[mid][mid] = a[mid];
if (mid + 1 <= r) {
dp[mid + 1][mid + 1] = a[mid + 1];
for (int i = mid + 2; i <= r; i++) dp[mid + 1][i] = Secret(dp[mid + 1][i - 1], a[i]);
}
for (int i = mid - 1; i >= l; i--) dp[mid][i] = Secret(a[i], dp[mid][i + 1]);
dnc(l, mid);
dnc(mid + 1, r);
}
void Init(int N, int A[]) {
n = N;
for (int i = 1; i <= n; i++) a[i] = A[i - 1];
dnc(1, n);
}
int make(int l, int r, int &L, int &R) {
if (l == r) return a[l];
int mid = (l + r) / 2;
if (R <= mid) return make(l, mid, L, R);
if (L > mid) return make(mid + 1, r, L, R);
int leftVal = dp[mid][L];
int rightVal = dp[mid + 1][R];
return Secret(leftVal, rightVal);
}
int Query(int L, int R) {
L++;
R++;
return make(1, n, L, R);
}
