#include <bits/stdc++.h>
#include "secret.h"
std::vector < std::vector < int > > sum;
std::vector < int > a;
// int Secret(int x, int y) {
// return x + y;
// }
void Divide(int lx, int rx) {
if (lx == rx) {
sum[lx][lx] = a[lx];
return;
}
if (lx > rx)
return;
int m = (lx + rx) / 2;
sum[m][m] = a[m];
sum[m + 1][m + 1] = a[m + 1];
for (int i = m - 1; i >= lx; i--)
sum[i][m] = Secret(a[i], sum[i + 1][m]);
for (int i = m + 2; i <= rx; i++)
sum[m + 1][i] = Secret(sum[m + 1][i - 1], a[i]);
Divide(lx, m - 1);
Divide(m + 1, rx);
}
int Get(int lx, int rx, int l, int r) {
int m = (lx + rx) / 2;
if (l <= m && m + 1 <= r) {
return Secret(sum[l][m], sum[m + 1][r]);
}
if (r <= m)
return Get(lx, m - 1, l, r);
return Get(m + 1, rx, l, r);
}
void Init(int N, int A[]) {
sum.resize(N, std::vector < int >(N));
a.resize(N);
for (int i = 0; i < N; i++)
a[i] = A[i];
Divide(0, N - 1);
}
int Query(int l, int r) {
return l == r ? a[l] : Get(0, a.size() - 1, l, r);
}
// int main() {
// std::ios::sync_with_stdio(0); std::cin.tie(0);
// int a[8] = { 1, 4, 7, 2, 5, 8, 3, 6 };
// Init(8, a);
// std::cout << Query(0, 3) << "\n";
// std::cout << Query(1, 7) << "\n";
// std::cout << Query(5, 5) << "\n";
// std::cout << Query(2, 4) << "\n";
// }
