#include "secret.h"
int prefix[1006][1006];
int n;
void precompute(int l,int r,int A[])
{
int mid = (l+r)/2;
prefix[mid][mid]=A[mid];
prefix[mid+1][mid+1]=A[mid+1];
for(int i=mid+2;i<=r;i++)
prefix[mid+1][i] = Secret(prefix[mid+1][i-1],A[i]);
for(int i=mid-1;i>=l;i--)
prefix[mid][i] = Secret(prefix[mid][i+1],A[i]);
if(mid+1<r)
precompute(mid+1,r,A);
if(mid>l)
precompute(l,mid,A);
}
void Init(int N, int A[])
{
n=N;
precompute(0,N-1,A);
}
int Query(int L, int R)
{
int l = 0, r = n-1;
while(l!=r)
{
int mid = (l+r)/2;
if(mid>=L && mid+1<=R)
return Secret(prefix[mid][L],prefix[mid+1][R]);
else if(mid==R)
return prefix[mid][L];
else if(mid<L)
l=mid+1;
else r=mid;
}
return prefix[l][l];
}
