#include "secret.h"
int n;
int pre[1010][1010] = {};
void process(int L, int R, int A[]) {
if(L == R) return;
int m = (L + R)/2;
pre[m][m] = A[m];
pre[m+1][m+1] = A[m+1];
int curr = pre[m][m];
for(int i = m-1; i >= L; i--) {
pre[m][i] = Secret(A[i], pre[m][i+1]);
}
curr = pre[m+1][m+1];
for(int i = m+2; i <= R; i++) {
pre[m][i] = Secret(curr, pre[m][i-1]);
}
process(L, m, A);
process(m+1, R, A);
}
void Init(int N, int A[]) {
n = N;
process(0, N-1, A);
}
int Query(int L, int R) {
int lo = 0, hi = n-1;
while(lo < hi) {
int mid = (lo + hi)/2;
if(L <= mid && R >= mid + 1) {
return Secret(pre[L][mid], pre[mid+1][R]);
} else if(R == mid) {
return pre[L][mid];
}
if(R < mid + 1) {
hi = mid;
} else {
lo = mid + 1;
}
}
return pre[lo][lo];
}
