#include <bits/stdc++.h>
#include "secret.h"
//#include "grader.cpp"
using namespace std;
#define all(x) x.begin(), x.end()
#define pb push_back
int n;
vector<int> a;
vector<vector<int>> pr, sf;
void dset(){
pr.resize(10000);
sf.resize(10000);
};
void build(int v, int l, int r){
if(v == 1){
l = 0, r = n-1;
}
sf[v].pb(a[r]);
for(int i = r-1; i >= l; i--){
sf[v].pb(Secret(a[i], sf[v].back()));
}
pr[v].pb(a[l]);
for(int i = l+1; i <= r; i++){
pr[v].pb(Secret(pr[v].back(), a[i]));
}
reverse(all(sf[v]));
if(l == r)return;
int m = (l+r)>>1;
build(v*2, l, m);
build(v*2+1, m+1, r);
};
int ask(int i, int l, int r, int tl, int tr){
if(i == 1){
l = 0, r = n-1;
}
int m = (l+r)>>1;
if(l == tl && tr == r)return pr[i].back();
if(tr <= m)return ask(i*2, l, m, tl, tr);
if(tl > m)return ask(i*2+1, m+1, r, tl, tr);
int il = i*2, ir = i*2+1;
// sf il
int vl = sf[il][m - tl];
// pr ir
int vr = pr[ir][tr - m];
return Secret(vl, vr);
};
void Init(int N, int A[]) {
n = N;
for(int i = 0; i < N; i++)a.pb(A[i]);
dset();
build(1,1,1);
}
int Query(int l, int r) {
return ask(1,1,1,l, r);
}
