#include "secret.h"
#include <bits/stdc++.h>
using namespace std;
int sum[1005][1005], val[1005], num;
void recur(int l, int r)
{
if (l==r)
{
sum[l][l]=val[l];
return;
}
int mid=(l+r)/2;
sum[mid][mid]=val[mid];
sum[mid+1][mid+1]=val[mid+1];
for (int i=mid-1; i>=l; i--)
sum[mid][i]=Secret(sum[mid][i+1], val[i]);
for (int i=mid+2; i<=r; i++)
sum[mid+1][i]=Secret(sum[mid+1][i-1], val[i]);
recur(l, mid);
recur(mid+1, r);
}
void Init(int n, int a[])
{
num=n;
for (int i=0; i<n; i++)
val[i]=a[i];
recur(0, n-1);
}
int Query(int l, int r)
{
int a=0, b=num-1;
while (a<b)
{
int mid=(a+b)/2;
if (l<=mid && mid<r)
return Secret(sum[mid][l], sum[mid+1][r]);
else if (r<=mid)
b=mid;
else
a=mid+1;
}
return sum[a][a];
}
