#include <bits/stdc++.h>
#include "secret.h"
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;
}
if(l == r){
pr[v].pb(a[l]);
sf[v].pb(a[r]);
return;
}
int m = (l+r)>>1;
build(v*2, l, m);
build(v*2+1, m+1, r);
pr[v] = pr[v*2 ];
for(int i = m+1; i <= r; i++) pr[v].pb(Secret(pr[v].back(), a[i]));
sf[v] = sf[v*2+1];
if(r-l == 1){
sf[v].pb(pr[v].back());
}
else
for(int i = m; i >= l; i--) sf[v].pb(Secret(a[i], sf[v].back()));
};
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;
int vl = sf[il][m - tl];
int vr = pr[ir][tr - m-1];
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);
}
