#include "secret.h"
#include <bits/stdc++.h>
using namespace std;
vector<vector<int>> dnc(11, vector<int>(1000));
vector<vector<int>> cnd(11, vector<int>(1000));
void divide(int l, int r, int v, int *a, int side) {
if (l == r) dnc[v][l] = cnd[v][l] = a[l];
else {
int m = (l + r) / 2;
divide(l, m, v + 1, a, side == -1 ? -1 : 0);
divide(m + 1, r, v + 1, a, side == 1 ? 1 : 0);
if (side != -1) {
for (int i = l; i <= m; i++) dnc[v][i] = dnc[v + 1][i];
for (int i = m + 1; i <= r; i++) dnc[v][i] = Secret(dnc[v][i - 1], a[i]);
}
if (side != 1) {
for (int i = r; i > m; i--) cnd[v][i] = cnd[v + 1][i];
for (int i = m; i >= l; i--) cnd[v][i] = Secret(a[i], cnd[v][i + 1]);
}
}
}
int nn, edgecase;
int conquer(int ll, int rr, int l, int r, int v) {
// cout << "dividng " << l << " " << r << endl;
if (l == r) return dnc[max(0, v - 1)][l];
int m = (l + r) / 2;
if (rr <= m) return conquer(ll, rr, l, m, v + 1);
else if (ll > m) return conquer(ll, rr, m + 1, r, v + 1);
return Secret(cnd[v][ll], dnc[v][rr]);
}
void Init(int n, int a[]) {
nn = n;
if (n == 1) {
edgecase = a[0];
return;
}
int m = (n - 1) / 2;
divide(0, m, 0, a, -1);
divide(m + 1, n - 1, 0, a, 1);
// cout << endl;
}
int Query(int l, int r) {
if (nn == 1) return edgecase;
// cout << "query" << endl;
return conquer(l, r, 0, nn - 1, 0);
}
