#include "secret.h"
const int mxn = 1010;
int n, range[mxn][mxn];
void build(int l, int r, int a[]) {
if(l == r) return;
// cout << "building: " << l << ' ' << r << '\n';
int m = (l + r) / 2;
int M = (l + r) / 2 + 1;
// cout << " > " << m << ' ' << M << '\n';
range[m][m] = a[m];
range[M][M] = a[M];
for(int i = M + 1; i <= r; i++)
range[M][i] = Secret(range[M][i - 1], a[i]);
for(int i = m - 1; i >= l; i--)
range[i][m] = Secret(a[i], range[i + 1][m]);
build(l, m, a);
build(M, r, a);
}
void Init(int n, int a[]) {
::n = n;
build(0, n - 1, a);
}
int Query(int L, int R) {
int l = 0, r = n - 1;
// cout << "e " << L << ' ' << R << '\n';
// cout << range[L][R] << '\n';
while(r - l > 1) {
int m = (l + r) / 2;
int M = (l + r) / 2 + 1;
if(L <= m && M <= R) {
return Secret(range[L][m], range[M][R]);
}
if(R <= m) r = m;
if(M <= L) l = M;
}
// cout << "sussy baka " << range[L][R] << '\n';
return range[L][R];
}
