#include "secret.h"
#include<vector>
using namespace std;
const int MX = 1005;
vector<int> L[MX], R[MX];
int B[MX], N;
void get_LR(int s, int e, int A[]){
if( s == e ) return;
int m = (s+e) / 2;
L[m].push_back(A[m]);
for(int i = m-1; i >= s; i--){
L[m].push_back(Secret(A[i], L[m].back()));
}
R[m].push_back(A[m+1]);
for(int i = m+2; i <= e; i++){
R[m].push_back(Secret(R[m].back(), A[i]));
}
get_LR(s, m, A);
get_LR(m+1, e, A);
}
void Init(int N, int A[]) {
::N = N;
get_LR(0, N-1, A);
for(int i = 0; i < N; i++) B[i] = A[i];
}
int get_answer(int s, int e, int l, int r){
int m = (s+e) / 2;
if( l <= m && m+1 <= r ){
return Secret(L[m][m-l], R[m][r-m-1]);
}
else if( m < l ) return get_answer(m+1, e, l, r);
else return get_answer(s, m, l, r);
}
int Query(int L, int R) {
if( L == R ) return B[L];
return get_answer(0, N-1, L, R);
}
