#include "secret.h"
#include<bits/stdc++.h>
const int MAXN = 1010;
int n;
long long value[MAXN][MAXN];
long long v[MAXN];
void dc(int ini, int fim){
if(ini == fim) {
value[ini][ini] = v[ini];
return;
}
int mid = (ini + fim) / 2;
dc(ini, mid);
dc(mid + 1, fim);
value[mid][mid] = v[mid];
for(int i = mid - 1; i >= ini; i--)
value[i][mid] = Secret(value[i + 1][mid], v[i]);
value[mid + 1][mid + 1] = v[mid + 1];
for(int i = mid + 2; i <= fim; i++)
value[mid + 1][i] = Secret(value[mid + 1][i - 1], v[i]);
}
long long getVal(int ini, int fim, int l, int r){
// printf("\t%d %d\n", ini, fim);
if(ini == fim) return value[ini][ini];
int mid = (ini + fim) / 2;
if(l <= mid && r > mid)
return Secret(value[l][mid], value[mid + 1][r]);
if(r <= mid)
return getVal(ini, mid, l, r);
return getVal(mid + 1, fim, l, r);
}
void Init(int N, int A[]) {
n = N;
for(int i = 0; i < n; i++)
v[i] = A[i];
dc(0, n - 1);
}
int Query(int L, int R) {
// printf("Query: %d %d\n", L, R);
if(L == R) return v[L];
return getVal(0, n - 1, L, R);
}
//g++ -o secret -O2 grader.cpp secret.cpp
