#include "secret.h"
#include <iostream>
#include <vector>
using namespace std;
//midpoint, endpoint
int res[1000][1000];
int N;
vector<int> A(1000);
void precompute(int a, int b)
{
if(a == b)
{
res[a][a] = A[a];
return;
}
if(a+1 == b)
{
res[a][b] = A[b];
res[a][a] = A[a];
return;
}
int m = (a+b)/2;
res[m][m+1] = A[m+1];
for(int i = m+2; i <= b; i++) res[m][i] = Secret(res[m][i-1], A[i]);
res[m][m] = A[m];
for(int i = m-1; i >= a; i--) res[m][i] = Secret(A[i], res[m][i+1]);
precompute(a, m);
precompute(m+1, b);
}
void Init(int n, int a[])
{
N = n;
for(int i = 0; i < N; i++) A[i] = a[i];
precompute(0, N-1);
}
int query1(int L, int R, int a, int b)
{
int m = (a+b)/2;
if(L <= m && m+1 <= R) return Secret(res[m][L], res[m][R]);
else if(R <= m) return query1(L, R, a, m);
else return query1(L, R, m+1, b);
}
int Query(int L, int R)
{
if(L == R) return A[L];
if(L+1 == R) return Secret(A[L], A[R]);
return query1(L, R, 0, N-1);
}
