#include "secret.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vll = vector <ll>;
using ii = pair <ll, ll>;
using vii = vector <ii>;
struct si { int v; };
si operator+ (si a, si b) { return si{ Secret(a.v, b.v) }; }
using vsi = vector <si>;
const ll MAXN = 1E3+16, LOG = 11;
si suff[LOG][MAXN], pref[LOG][MAXN];
vsi ve;
#define mid ((l+r)>>1)
void finit (ll l, ll r, ll lvl) {
suff[lvl][mid] = ve[mid];
for (ll i = mid-1; i >= l; i--)
suff[lvl][i] = ve[i] + suff[lvl][i+1];
pref[lvl][mid+1] = ve[mid+1];
for (ll i = mid+2; i <= r; i++)
pref[lvl][i] = pref[lvl][i-1] + ve[i];
if (l == r) return;
finit(l, mid, lvl+1);
finit(mid+1, r, lvl+1);
}
ll n;
void Init (int n, int a[]) {
::n = n;
ve = vsi(n, si{ 0 });
for (ll i = 0; i < n; i++) ve[i] = si{ a[i] };
finit(0, n-1, 0);
}
si fsolve (ll ql, ll qr, ll l, ll r, ll lvl) {
if (ql <= mid && mid+1 <= qr) {
return suff[lvl][ql] + pref[lvl][qr];
}
if (qr <= mid)
return fsolve(ql, qr, l, mid, lvl+1);
else
return fsolve(ql, qr, mid+1, r, lvl+1);
}
int Query (int ql, int qr) {
if (ql == qr) return ve[ql].v;
return fsolve(ql, qr, 0, n-1, 0).v;
}
