#include "secret.h"
int pre[1000][1000], n;
void d(int L, int R, int A[]){
int mid = (L + R) / 2;
pre[mid][mid] = A[mid];
pre[mid + 1][mid + 1] = A[mid + 1];
for (int i = mid + 2; i <= R; i++){
pre[mid + 1][i] = Secret(pre[mid + 1][i - 1], A[i]);
}
for (int i = mid - 1; i >= L; i--){
pre[mid][i] = Secret(pre[mid][i + 1], A[i]);
}
if (L < mid) d(L, mid, A);
if (mid + 1 < R) d(mid + 1, R, A);
}
void Init(int N, int A[]) {
n = N;
d(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(pre[mid][L], pre[mid + 1][R]);
else if (mid == R) return pre[mid][L];
else if (mid < L) a = mid + 1;
else b = mid;
}
return pre[a][a];
}
