/*
ID: USACO_template
LANG: C++
PROG: USACO
*/
#include <iostream> //cin , cout
#include <fstream> //fin, fout
#include <stdio.h> // scanf , pringf
#include <cstdio>
#include <algorithm> // sort , stuff
#include <stack> // stacks
#include <queue> // queues
#include <map>
#include <string>
#include "secret.h"
using namespace std;
typedef pair<int, int> pii;
typedef vector<int> vi; /// adjlist without weight
typedef vector<pii> vii; /// adjlist with weight
typedef vector<pair<int,pii>> vpip; /// edge with weight
typedef long long ll;
#define mp make_pair
#define fst first
#define snd second
#define pb push_back
#define trav(u, adj_v) for (auto& u: adj_v)
const int MOD = 1e9+7; // 998244353;
const int MX = 2e5+5; //
const ll INF = 1e18; //
#define MAXV 1007
#define MAXE 100007
bool debug = false, submit = true;
/**
* RMQ use sparse table, O(N log N) memory and setip, O(1) query
* https://usaco.guide/plat/DC-SRQ
*/
int rqN;
int x[MAXV];
int rq[MAXV][MAXV]; /// 18 = ceil(log2(n))
void divi(int l, int r, int lev = 0) { // generate dat and mask
if (l == r) { rq[lev][l] = x[l]; return; }
int m = (l+r)/2;
rq[lev][m] = x[m]; for(int i = m-1; i >= l; i--) rq[lev][i] = Secret(x[i], rq[lev][i+1]);
rq[lev][m+1] = x[m+1]; for(int i = m+2; i <= r; i++) rq[lev][i] = Secret(rq[lev][i-1], x[i]);
divi(l,m,lev+1); divi(m+1,r,lev+1);
}
int que(int ql, int qr, int lev = 0, int l = 0, int r = rqN -1) { /// [ , ]
if(l == r) return x[l];
int m = (l+r)/2;
if(ql <= m && m <= qr) return Secret(rq[lev][ql], rq[lev][qr]);
if(qr <= m) return que(ql, qr, lev+1, l, m);
else return que(ql, qr, lev+1, m+1, r);
}
void Init(int N, int A[]) {
rqN = N;
for(int i = 0; i < N; i++) x[i]= A[i];
divi(0, N-1);
}
int Query(int L, int R) {
que(L, R);
}
