#include "secret.h"
const int N = 1000;
int res[N][N], n;
void precompute(int l, int r, int a[]) {
int mid = (l + r) / 2;
res[mid][mid] = a[mid];
res[mid + 1][mid + 1] = a[mid + 1];
for (int i = mid + 2; i <= r; ++i)
res[mid + 1][i] = Secret(res[mid + 1][i - 1], a[i]);
for (int i = mid - 1; i >= l; --i)
res[mid][i] = Secret(a[i], res[mid][i + 1]);
if (l < mid) precompute(l, mid, a);
if (mid + 1 < r) precompute(mid + 1, r, a);
}
void Init(int N, int A[]) {
n = N;
precompute(0, n - 1, A);
}
int Query(int L, int R) {
int a = 0, b = n - 1;
while (a != b) {
int mid = (a + b) / 2;
if (mid >= L && mid < R)
return Secret(res[mid][L], res[mid + 1][R]);
else if (mid == R)
return res[mid][L];
else if (mid < L)
a = mid + 1;
else
b = mid;
}
return res[a][a];
}
