#include <bits/stdc++.h>
#include "secret.h"
using namespace std;
#define name "TENBAI"
#define fi first
#define se second
// #define int long long
#define endl '\n'
#define setmin(x, y) x = min((x), (y))
#define setmax(x, y) x = max((x), (y))
#define sqr(x) ((x) * (x))
mt19937 hdp(chrono::high_resolution_clock::now().time_since_epoch().count());
int rand(int l, int r){return l + ((hdp() % (r - l + 1)) + r - l + 1) % (r - l + 1);}
const int NM = 1e3 + 5;
map<pair<int, int>, int> mp;
int n, a[NM], sum = 0;
pair<int, int> b[NM][NM];
// int Secret(int x, int y)
// {
// return x + y;
// }
void dnc(int l, int r)
{
if (l >= r)
return;
int m = l + r >> 1;
for (int i = m - 1; i >= l; i--)
mp[{i, m}] = Secret(a[i], mp[{i + 1, m}]);
for (int i = m + 2; i <= r; i++)
mp[{m + 1, i}] = Secret(mp[{m + 1, i - 1}], a[i]);
for (int i = l; i <= m; i++)
for (int j = m + 1; j <= r; j++)
b[i][j] = {mp[{i, m}], mp[{m + 1, j}]};
dnc(l, m);
dnc(m + 1, r);
}
void Init(int N, int A[])
{
n = N;
for (int i = 1; i <= n; i++)
{
a[i] = A[i - 1];
mp[{i, i}] = a[i];
}
dnc(1, n);
}
int Query(int l, int r)
{
l++; r++;
if (l == r)
return a[l];
return Query(b[l][r].fi, b[l][r].se);
}
// signed main()
// {
// Init(2, );
// cout << Query(0, 1);
// }
