#include "secret.h"
#include <bits/stdc++.h>
using namespace std;
struct node {
int s,e,m;
vector<int> pre, suf;
node *l, *r;
node (int S, int E, int A[]){
s=S, e=E, m=(s+e)/2;
if(s==e){
suf.push_back(A[s]);
return;
}
l=new node(s,m,A);
r=new node(m+1,e,A);
suf.push_back(A[m]);
pre.push_back(A[m+1]);
for(int i=m-1;i>=s;i--){
suf.push_back(Secret(A[i], suf.back()));
}
for(int i=m+2;i<=e;i++){
pre.push_back(Secret(pre.back(),A[i]));
}
}
int query(int S, int E){
if(s==e)return suf[0];
if(S > m)return r->query(S,E);
else if(E<=m)return l->query(S,E);
return Secret(suf[m-S], pre[E-m-1]);
}
} *root;
void Init(int N, int A[]) {
root=new node(0, N-1, A);
}
int Query(int L, int R) {
return root->query(L,R);
}
