#include <bits/stdc++.h>
#pragma GCC optimize ("Ofast")
#pragma GCC target ("avx2")
#include "secret.h"
using namespace std;
using ll = long long;
using vi = vector<int>;
#define pb push_back
#define ff first
#define ss second
#define lb lower_bound
#define all(x) (x).begin() , (x).end()
int st[2555][2555], arr[2555], n;
void build(int L, int R) {
int md = (L + R)/2;
st[md][md] = arr[md];
st[md + 1][md + 1] = arr[md + 1];
for(int l = md + 2; l <= R; l++)
st[md + 1][l] = Secret(st[md + 1][l - 1], arr[l]);
for(int l = md - 1; l >= L; l--)
st[md][l] = Secret(arr[l], st[md][l+1]);
if(L < md) build(L, md);
if(md + 1 < R) build(md + 1, R);
}
void Init(int N, int A[]) {
n = N;
for(int l = 0; l < n; l++) arr[l] = A[l];
build(0, n-1);
}
int Query(int L, int R) {
int l = 0, r = n - 1;
while(l != r) {
int md = (l+r)/2;
if(md >= L && md < R)
return Secret(st[md][L], st[md+1][R]);
else if(md == R) return st[md][L];
else if(md < L) l = md + 1;
else r = md;
}
return st[l][l];
}
