#include "secret.h"
#include <iostream>
int pref[1100][1100];
int suff[1100][1100];
int a[1100];
void build(int c,int l,int r){
if(l==r){
pref[c][l]=a[l];
return;
}
int mid=(l+r)/2;
pref[c][mid+1]=a[mid+1];
suff[c][mid]=a[mid];
for(int i=mid+2;i<=r;i++)pref[c][i]=Secret(pref[c][i-1],a[i]);
for(int i=mid-1;i>=l;i--)suff[c][i]=Secret(a[i],suff[c][i+1]);
// std::cout << c << ' ' << l << ' ' << r << '\n';
// for(int i=l;i<=mid;i++)std::cout << suff[c][i] << ' ';
// std::cout << '|';
// for(int i=mid+1;i<=r;i++)std::cout << pref[c][i] << ' ';
// std::cout << '\n';
build(c*2,l,mid);
build(c*2+1,mid+1,r);
}
int ans(int c,int l,int r,int ql,int qr){
//std::cout << l << ' ' << r << ' ' << ql << ' ' << qr << '\n';
int mid=(l+r)/2;
if(ql<=mid&&mid<=qr){
if(qr==mid)return suff[c][ql];
return Secret(suff[c][ql],pref[c][qr]);
}
else if(qr<mid)return ans(c*2,l,mid,ql,qr);
else if(ql>mid)return ans(c*2+1,mid+1,r,ql,qr);
return -1;
}
int gN;
void Init(int N, int A[]) {
gN=N;
for(int i=1;i<=N;i++)a[i]=A[i-1];
build(1,1,N);
}
int Query(int L, int R) {
return ans(1,1,gN,L+1,R+1);
}
