#include "secret.h"
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
ll Secret(ll x ,ll y){
return x + y;
}
const int N = 1000;
ll it[4 * N][N + 5];
ll a[N + 5];
int n;
void build(int id, int l, int r){
if(l >= r) return;
int mid = (l + r) >> 1;
it[id][mid] = a[mid];
it[id][mid - 1] = a[mid - 1];
for(int i = mid - 2 ; i >= l ; --i) it[id][i] = Secret(it[id][i + 1],a[i]);
for(int i = mid + 1 ; i <= r ; ++i) it[id][i] = Secret(it[id][i - 1],a[i]);
build(id << 1,l,mid - 1);
build(id << 1 | 1,mid + 1,r);
}
ll get(int id, int l, int r, int u, int v){
int mid = (l + r) >> 1;
if(u <= mid && mid <= v) return Secret(it[id][u],it[id][v]);
if(mid < u) return get(id << 1 | 1,mid + 1,r,u,v);
else return get(id << 1,l,mid - 1,u,v);
}
void Init(int nn, int A[]){
n = nn;
for(int i = 1 ; i <= n ; ++i) a[i] = A[i - 1];
build(1,1,n);
}
int Query(int l, int r){
l++;r++;
if(l > r) swap(l,r);
if(l == r) return a[l];
return get(1,1,n,l,r);
}
