#include "secret.h"
#include <bits/stdc++.h>
// #include <sys/resource.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;
assert(ans[m][m] != -1);
for(int i = m - 1; i >= l; i--){
if(ans[i][m] != -1) continue;
ans[i][m] = Secret(ans[i + 1][m], a[i]);
}
for(int i = m + 1; i <= r; i++){
if(ans[m][i] != -1) continue;
ans[m][i] = Secret(ans[m][i - 1], a[i]);
}
divide_and_conquer(l, m);
divide_and_conquer(m + 1, r);
}
void Init(int N, int A[]) {
// 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);
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++;
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 Secret(ans[L][m], ans[m + 1][R]);
}
}
// assert(0);
return 0;
}
