#include "secret.h"
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1000;
int ans[MAXN*(MAXN+1)/2];
int L[MAXN], R[MAXN];
vector<pair<int, int>> Q;
map<pair<int, int>, int> P;
void dnc(int l, int r, vector<int> V, int A[]) {
if (V.empty()) return;
if (l == r) {
for (auto &e : V) ans[e] = A[l];
return;
}
int mid = (l + r) / 2;
L[mid] = A[mid];
R[mid+1] = A[mid+1];
for (int i = mid-1; i >= l; i--) L[i] = Secret(A[i], L[i+1]);
for (int i = mid+2; i <= r; i++) R[i] = Secret(R[i-1], A[i]);
vector<int> V1, V2;
for (auto &e : V) {
int a = Q[e].first, b = Q[e].second;
if (a <= mid && mid < b) { ans[e] = Secret(L[a], R[b]); continue; }
if (a <= mid) V1.emplace_back(e);
else V2.emplace_back(e);
}
dnc(l, mid, V1, A);
dnc(mid+1, r, V2, A);
}
void Init(int N, int A[]) {
for (int i = 0; i < N; i++) {
for (int j = i; j < N; j++) {
Q.emplace_back(i, j);
P[{i, j}] = Q.size() - 1;
}
}
vector<int> V;
for (int i = 0; i < N * (N+1) / 2; i++) V.emplace_back(i);
dnc(0, N-1, V, A);
}
int Query(int L, int R) { return ans[P[{L, R}]]; }
