//
// dncRQ.hpp
// EliteCamp 2025
//
// Created by Ali AlSalman on 19/11/2025.
//
#include <bits/stdc++.h>
template<typename T>
using vec = std::vector<T>;
using namespace std;
int Secret(int x, int y);
struct dncRQ {
int n, mx_d;
vec<vec<int>> S;
vec<int> M;
private:
int _merge(int lhs, int rhs) {
return Secret(lhs, rhs);
}
void _init(int l, int r, vec<int> &a, int d = 0, int mask = 0) {
if (l + 1 == r) {
M[l] = mask;
S[d][l] = a[l]; mx_d = d;
return;
}
int mid = (l + r) / 2;
S[d][mid - 1] = a[mid - 1];
S[d][mid] = a[mid];
for (int i = mid + 1; i < r; i++)
S[d][i] = _merge(S[d][i - 1], a[i]);
for (int i = mid - 2; l <= i; i--)
S[d][i] = _merge(a[i], S[d][i + 1]);
_init(l, mid, a, d + 1, mask|(1<<d));
_init(mid, r, a, d + 1, mask|(0<<d));
}
public:
dncRQ(vec<int> &arr) {
n = (int) arr.size();
S.resize(33, vec<int>(n));
M.resize(n);
_init(0, (int) arr.size(), arr);
}
int query(int l, int r) {
if (l == r)
return S[mx_d][l];
int lm = M[l], rm = M[r];
int d = __builtin_ctz(lm ^ rm);
return _merge(S[d][l], S[d][r]);
}
};
dncRQ *rq;
void Init(int n, int a[]) {
vec<int> arr(a, a + n);
rq = new dncRQ(arr);
}
int Query(int l, int r) {
return rq->query(l, r);
}
