#include "secret.h"
const int MAXN = 1000;
int size = 0;
int precalc[MAXN][MAXN];
void dc(int left, int right)
{
if (right - left <= 1)
return;
int middle = (left + right) / 2;
for (int iElem = middle + 1; iElem < right; iElem++)
precalc[middle][iElem] = Secret(precalc[middle][iElem - 1], precalc[iElem][iElem]);
for (int iElem = middle - 2; iElem >= left; iElem--)
precalc[iElem][middle - 1] = Secret(precalc[iElem][iElem], precalc[iElem + 1][middle - 1]);
dc(left, middle);
dc(middle + 1, right);
}
void Init(int N, int A[])
{
size = N;
for (int iElem = 0; iElem < N; iElem++)
precalc[iElem][iElem] = A[iElem];
dc(0, N);
}
int searchmid(int left, int right, int ql, int qr)
{
int mid = (left + right) / 2;
if (qr < mid)
return searchmid(left, mid, ql, qr);
if (ql > mid)
return searchmid(mid + 1, right, ql, qr);
return mid;
}
int Query(int L, int R)
{
int mid = searchmid(0, size, L, R);
if (L < mid)
return Secret(precalc[L][mid - 1], precalc[mid][R]);
return precalc[mid][R];
}
