#include "secret.h"
#include <bits/stdc++.h>
using namespace std;
#define MOD 1000000007
#define fir first
#define sec second
#define pushf push_front
#define pushb push_back
#define popf pop_front
#define popb pop_back
#define mp make_pair
#define all(a) a.begin(), a.end()
#define FOR(i, s, e) for(int i = s; i < e; i++)
#define RFOR(i, s, e) for(int i = e-1; i >= s; i--)
#define REP(i, n) FOR(i, 0, n)
#define RREP(i, n) RFOR(i, 0, n)
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef pair<ll, ll> pll;
typedef vector<ll> vll;
typedef vector<bool> vb;
typedef vector<char> vc;
typedef vector<string> vs;
typedef vector<pii> vpii;
typedef vector<pll> vpll;
typedef vector<vi> vvi;
typedef vector<vll> vvll;
typedef vector<vb> vvb;
typedef vector<vc> vvc;
typedef vector<vpii> vvpii;
typedef vector<vpll> vvpll;
typedef queue<int> qi;
typedef queue<ll> qll;
typedef queue<pii> qpii;
typedef queue<pll> qpll;
typedef deque<int> dqi;
typedef deque<ll> dqll;
typedef deque<pii> dqpii;
typedef deque<pll> dqpll;
typedef priority_queue<int> pqi;
typedef priority_queue<ll> pqll;
typedef priority_queue<pii> pqpii;
typedef priority_queue<pll> pqpll;
typedef priority_queue<int, vi, greater<int> > r_pqi;
typedef priority_queue<ll, vll, greater<ll> > r_pqll;
typedef priority_queue<pii, vpii, greater<pii> > r_pqpii;
typedef priority_queue<pll, vpll, greater<pll> > r_pqpll;
int n;
vi arr;
const int MN = 1005;
int dp[11][MN];
void precompute(int l, int r, int t) {
int m = (l + r) / 2;
dp[t][m] = arr[m];
if(l == r) {
return;
}
//cerr<<l<<' '<<r<<endl;
RFOR(i, l, m) {
dp[t][i] = Secret(arr[i], dp[t][i+1]);
}
dp[t][m+1] = arr[m+1];
FOR(i, m+2, r+1) {
dp[t][i] = Secret(dp[t][i-1], arr[i]);
}
precompute(l, m, t+1);
precompute(m+1, r, t+1);
}
void Init(int N, int A[]) {
n = N;
arr = vi(n);
REP(i, n) {
arr[i] = A[i];
}
memset(dp, 0, sizeof(dp));
precompute(0, n-1, 0);
/*
REP(i, 10) {
REP(j, n) {
cerr<<dp[i][j]<<' ';
}
cerr<<endl;
}
*/
}
int qry(int l, int r, int t, int s, int e) {
int m = (l + r) / 2;
if(l == r) {
//cerr<<l<<' '<<r<<' '<<t<<' ';
return arr[s];
}
if(m >= e) {
return qry(l, m, t+1, s, e);
}
else if(m < s) {
return qry(m+1, r, t+1, s, e);
}
//cerr<<l<<' '<<r<<' '<<t<<' ';
return Secret(dp[t][s], dp[t][e]);
}
int Query(int L, int R) {
return qry(0, n-1, 0, L, R);
}
