#include "secret.h"
#include <bits/stdc++.h>
// #include <sys/resource.h>
using namespace std;
int ans[1001][1001], a[1001], n;
void divide_and_conquer(int l, int r){
if(r - l == 1){
return;
}
int m = (l + r) / 2;
divide_and_conquer(l, m);
divide_and_conquer(m, r);
ans[m - 1][m - 1] = a[m - 1];
for(int i = m - 2; i >= l; i--){
if(ans[i][m - 1] != -1) continue;
ans[i][m - 1] = Secret(ans[i + 1][m - 1], a[i]);
}
ans[m][m] = a[m];
for(int i = m + 1; i < r; i++){
if(ans[m][i] != -1) continue;
ans[m][i] = Secret(ans[m][i - 1], a[i]);
}
}
void Init(int N, int A[]) {
n = N;
// increase_stack_size(512L * 1024L * 1024L);
for(int i = 1; i <= N; i++){
a[i] = A[i - 1];
}
for(int i = 1; i <= N; i++){
for(int j = 1; j <= N; j++){
ans[i][j] = -1;
}
ans[i][i] = a[i];
}
divide_and_conquer(1, N + 1);
// for(int i = 1; i <= N; i++){
// for(int j = 1; j <= N; j++){
// cerr << ans[i][j] << ' ';
// }
// cerr << endl;
// }
}
int Query(int L, int R) {
L++, R++;
int l = 1, r = n;
while(l <= r){
int m = (l + r) / 2;
if(L <= m && m < R) return Secret(ans[l][m], ans[m + 1][R]);
if(m == R) return ans[L][m];
if(m < l) l = m + 1;
else r = m - 1;
}
return a[l];
}
