#include "secret.h"
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1024;
const int max_log = 15;
int n;
int a[maxn];
int precompute[maxn][max_log];
void divide(int depth, int l, int r)
{
if (l == r)
{
precompute[l][depth] = a[l];
return;
}
int mid = (l + r) / 2;
precompute[mid][depth] = a[mid];
for (int i = mid - 1; i >= l; --i)
{
precompute[i][depth] = Secret(precompute[i + 1][depth], a[i]);
}
precompute[mid + 1][depth] = a[mid + 1];
for (int i = mid + 2; i <= r; ++i)
{
precompute[i][depth] = Secret(precompute[i - 1][depth], a[i]);
}
divide(depth + 1, l, mid);
divide(depth + 1, mid + 1, r);
}
void Init(int N, int Arr[])
{
n = N;
for (int i = 0; i < n; ++i)
{
a[i] = Arr[i];
}
divide(0, 0, n - 1);
}
int recurse(int depth, int l, int r, int ql, int qr)
{
//cout << l << ' ' << r << ' ' << ql << ' ' << qr << endl;
if (l == r)
{
return precompute[l][depth];
}
int mid = (l + r) / 2;
if (qr <= mid)
{
return recurse(depth + 1, l, mid, ql, qr);
}
if (ql >= mid + 1)
{
return recurse(depth + 1, mid + 1, r, ql, qr);
}
//cout << "here for " << l << " and " << r << endl;
return Secret(precompute[l][depth], precompute[r][depth]);
}
int Query(int L, int R)
{
int l = L;
int r = R;
//cout << "-------------------------" << endl;
return recurse(0, 0, n - 1, l, r);
}
