#include "secret.h"
#define MAX_N 1000
int peal[MAX_N + 1][MAX_N + 1];
void Solve(int left, int right)
{
int mid, i;
if (right - left <= 1)
{
return;
}
mid = (left + right) / 2;
for (i = mid - 1; i >= left; --i)
{
if (peal[i][mid] == -1)
{
peal[i][mid] = Secret(peal[i][i + 1], peal[i + 1][mid]);
}
}
for (i = mid + 1; i <= right; ++i)
{
if (peal[mid][i] == -1)
{
peal[mid][i] = Secret(peal[mid][i - 1], peal[i - 1][i]);
}
}
Solve(left, mid);
Solve(mid, right);
}
void Init(int N, int A[])
{
int i, j;
for (i = 0; i <= N; ++i)
{
for (j = 0; j <= N; ++j)
{
peal[i][j] = -1;
}
}
for (i = 0; i < N; ++i)
{
peal[i][i + 1] = A[i];
}
Solve(0, N);
}
int Query(int L, int R)
{
int i;
for (i = L + 1; i <= R; ++i)
{
if (peal[L][i] != -1 && peal[i][R + 1] != -1)
{
return Secret(peal[L][i], peal[i][R + 1]);
}
}
return peal[L][R + 1];
}
