#include<bits/stdc++.h>
#include<algorithm>
#include<random>
#include<chrono>
#include<cstdlib>
#include<ctime>
#include<numeric>
#include<vector>
#include<stack>
#include<map>
#include<set>
#include<queue>
#include<iomanip>
#define int long long
#define ll long long
#define fi first
#define se second
#define pii pair<int,int>
#define sz(a) ((int)a.size())
#define FOR(i,j,k) for(int i=j;i<=k;i++)
#define REP(i,k,j) for(int i=k;i>=j;i--)
#define FORD(i,a) for(auto i:a)
#define rngdcl mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count())
#define random(l,r) ((l)+(rng()%(r-l+1)))
using namespace std;
const int nmax=1001;
int n;
int a[nmax],pfx[12][nmax],suf[12][nmax];
void dnc(int l,int r,int lv)
{
if(l==r)
{
suf[lv][l]=a[l];
return;
}
int mid=(l+r)/2;
//precase
suf[lv][mid]=a[mid];
pfx[lv][mid+1]=a[mid+1];
//build
REP(i,mid-1,l) suf[lv][i]=Secret(suf[lv][i+1],a[i]);
FOR(i,mid+2,r) pfx[lv][i]=Secret(pfx[lv][i-1],a[i]);
//recursion
dnc(l,mid,lv+1);
dnc(mid+1,r,lv+1);
}
void Init(int N, int A[])
{
n=N;
FOR(i,1,n) a[i]=A[i-1];
dnc(1,n,1);
}
pii find(int l,int r,int lv,int lf,int rt)
{
int mid=(l+r)/2;
if(l<=lf && rt<=r && lf<=mid && mid<=rt) return {lv,mid};
if(l<=lf && rt<=mid) return find(l,mid,lv+1,lf,rt);
else return find(mid+1,r,lv+1,lf,rt);
}
int Query(int L,int R)
{
int l=L+1,r=R+1;
auto save=find(1,n,1,l,r);
if(r==save.se) return suf[save.fi][l];
else return Secret(suf[save.fi][l],pfx[save.fi][r]);
}
