#include <bits/stdc++.h>
#include "secret.h"
#define ll long long
using namespace std;
const int M=1e3+5;
ll n,a[M],ans[M][M];
void Go(int l,int r) {
if (r-l<2) return ;
int mid=(l+r)/2;
// left segment l...mid
// right segment mid+1...r
for (int i=mid-1; i>=l; i--)
ans[i][mid]=Secret(ans[i+1][mid],a[i]);
for (int i=mid+2; i<=r; i++)
ans[mid+1][i]=Secret(ans[mid+1][i-1],a[i]);
Go(l,mid);
Go(mid+1,r);
}
void Init(int N, int A[]) {
n=N;
for (int i=0; i<n; i++) {
a[i]=A[i];
ans[i][i]=a[i];
}
Go(0,n-1);
}
int ansL,ansR;
int Get(int l,int r) {
if (r-l<2) return 0;
if (!(l<=ansL && ansR<=r)) return 0;
int mid=(l+r)/2;
if (ansL<=mid && mid+1<=ansR) {
return Secret(ans[ansL][mid],ans[mid+1][ansR]);
}
return Get(l,mid)+Get(mid+1,r);
}
int Query(int L, int R) {
if (L==R) return ans[L][R];
if (R-L==1) return Secret(a[R],a[L]);
ansL=L,ansR=R;
return Get(0,n-1);
}
