#include "secret.h"
#include <iostream> // cin, cout
#include <vector> // vector
#include <string> // string
#include <set>
#include <queue>
#include <fstream>
#include <unordered_map>
#include <algorithm>
#include <map>
#define vec vector
#define NEK 1000000000
#define For(i,n) for(ll i = 0; i < n; i++)
#define ld long double
#define ll long long
#define pii pair<int,int>
#define mod 1000000007
#define SIG 0.000001
using namespace std;
int msb(int x){
return 31 - __builtin_clz(x);
}
vec<vec<int>> hod;
vec<int> a;
void Init(int n, int*A){
For(i, n) a.push_back(A[i]);
hod.resize(32, vec<int>(n, NEK));
For(i, n-1){
int x = msb(i ^ (i+1));
int pol = 1<<x;
hod[x][i] = a[i];
for(int j = i-1; (j > (i - pol)) && j >= 0; j--){
hod[x][j] = Secret(hod[x][j+1], a[j]);
}
hod[x][i+1] = a[i+1];
for(int j = i+2; (j <= (i + pol)) && j < n; j++){
hod[x][j] = Secret(hod[x][j-1], a[j]);
}
}
}
int Query(int l, int r){
if(l == r) return a[l];
int x = msb(l ^ r);
return Secret(hod[x][l], hod[x][r]);
}
