#include "secret.h"
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
using namespace std;
int v[1010];
int arb[4010][1010]; // nod , pos
int n;
void prop (int nod , int st , int dr){
if (st == dr){
arb[nod][st] = v[st];
return;
}
int mij = st + dr;
mij /= 2;
prop (nod * 2 , st , mij);
prop (nod * 2 + 1 , mij + 1 , dr);
arb[nod][mij] = v[mij];
arb[nod][mij+1] = v[mij+1];
for (int i=mij+2; i<=dr; i++){
arb[nod][i] = Secret (arb[nod][i-1] , v[i]);
}
for (int i=mij-1; i>=st; i--){
arb[nod][i] = Secret (v[i] , arb[nod][i+1]);
}
}
void Init(int N, int A[]) {
n = N;
for (int i=0; i<n; i++){
v[i+1] = A[i];
}
prop (1 , 1 , n);
}
int query (int nod , int st , int dr , int MIN , int MAX){
int mij = st + dr;
mij /= 2;
if (MIN <= mij && MAX >= mij){
//cout<<MIN<<" "<<MAX<<" "<<mij<<'\n';
int ret = arb[nod][MIN];
if (MAX > mij){
ret = Secret (ret , arb[nod][MAX]);
}
return ret;
}
if (MAX < mij){
return query (nod * 2 , st , mij , MIN , MAX);
}
else{
return query (nod * 2 + 1 , mij + 1 , dr , MIN , MAX);
}
}
int Query(int L, int R) {
return query (1 , 1 , n , L+1 , R+1);
}
