#include <bits/stdc++.h>
#include "secret.h"
using namespace std;
map<pair<int,int>,int> mp;
int mySecret(int X, int Y){
if (!mp.count({X,Y}))mp[{X,Y}]=Secret(X,Y);
return mp[{X,Y}];
}
vector<int> lft[1003];
vector<int> rght[1003];
int wej[1003];
int n;
void build(int l, int p){
if (l==p)return;
int md=(l+p)/2;
lft[md].push_back(wej[md]);
for (int i = md-1; i>=l; i--){
lft[md].push_back(mySecret(wej[i],lft[md].back()));
}
rght[md+1].push_back(wej[md+1]);
for (int i = md+2; i<=p; i++){
rght[md+1].push_back(mySecret(rght[md+1].back(),wej[i]));
}
build(l,md);
build(md+1,p);
}
void Init(int N, int A[]){
for (int i = 0; i<N; i++)wej[i]=A[i];
n=N;
build(0,N-1);
}
int find(int l, int p){
int a=0,b=n-1,md=(a+b)/2;
while(l>md || p<=md){
if (l>md)a=md+1;
else b=md;
md=(a+b)/2;
}
return md;
}
int Query(int l, int p){
if (l==p)return wej[l];
int mid=find(l,p);
return mySecret(lft[mid][mid-l],rght[mid+1][p-mid-1]);
}
