#define f first
#define s second
#include "secret.h"
#include <bits/stdc++.h>
using namespace std;
const int N = 1005;
map<pair<int,int> ,int> mp;
int nn;
struct tree{
int seg[4*N];
int *a;
void build(int cur,int l,int r) {
if(l==r)mp[{l,l}]=seg[cur] = a[l];
else {
int mid = (l+r)/2;
build(cur*2,l,mid);
build(cur*2+1,mid+1,r);
mp[{l,r}]=seg[cur]=Secret(seg[cur*2],seg[cur*2+1]);
}
}
void process(int cur,int l,int r) {
if(abs(l-r) < 2) return;
int mid = (l+r)/2;
process(cur*2,l,mid);process(cur*2+1,mid+1,r);
// left side
int cnt = seg[cur*2];
if(l!=0){
for(int i = mid+1;i<r;i++){
if(!mp[{l,i}])mp[{l,i}]=Secret(cnt,a[i]);
cnt = mp[{l,i}];
}
}
cnt = seg[cur*2+1];
if(r!=nn-1){
for(int i = mid;i>l;i--){
if(!mp[{i,r}])mp[{i,r}]=Secret(a[i],cnt);
cnt = mp[{i,r}];
}
}
}
int qry(int cur,int ll,int rr,int l = 0,int r = nn-1) {
if(l > rr || r < ll) return -1;
int res;
int bl = max(ll,l),br = min(rr,r);
if(mp[{bl,br}])res = mp[{bl,br}];
else {
int mid = (l + r) / 2;
int a = qry(cur*2,ll,rr,l,mid), b = qry(cur*2+1,ll,rr,mid+1,r);
if(a==-1 || b==-1)res = (a==-1?b:a);
else res = Secret(a,b);
}
// cout << l << " " << r << " " << res << "\n";
return res;
}
}t;
void Init(int n, int a[]) {
t.a=a;
nn=n;
t.build(1,0,n-1);
t.process(1,0,n-1);
// for(auto a : mp)cout<<a.f.f<<" " << a.f.s << " " << a.s << '\n';
}
int Query(int l, int r) {
return t.qry(1,l,r);
}
/*
g++ -O2 -std=c++11 -o grader grader.cpp secret.cpp
*/
