#include "secret.h"
#include <bits/stdc++.h>
using namespace std;
int ans[1001][1001], a[1001];
void divide_and_conquer(int l, int r){
if(l > r) return;
if(l + 1 == r){
ans[l][r] = Secret(a[l], a[r]);
return;
}
int m = (l + r) / 2;
divide_and_conquer(l, m);
divide_and_conquer(m + 1, r);
ans[l][r] = Secret(ans[l][m], ans[m + 1][r]);
}
void Init(int N, int A[]) {
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);
}
int Query(int L, int R) {
L++, R++;
if(ans[L][R] != -1) return ans[L][R];
for(int m = L; m < R; m++){
if(ans[L][m] != -1 && ans[m + 1][R] != -1){
return ans[L][R] = Secret(ans[L][m], ans[m + 1][R]);
}
}
for(int m = R - 1; m >= L; m--){
if(ans[L][m] != -1){
int j = m + 1;
int cur = ans[L][m];
while(j <= R && ans[j][R] == -1){
cur = Secret(cur, a[j]);
j++;
}
if(j <= R){
return Secret(cur, ans[j][R]);
}
}
}
return 0;
}
