#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define popcount __builtin_popcount
#define all(a) (a).begin(), (a).end()
using namespace std;
using namespace chrono;
using namespace __gnu_pbds;
template<typename T> using ordered_set = tree<T,null_type,less_equal<>,rb_tree_tag,tree_order_statistics_node_update>;
#include "secret.h"
vector<int> lay[20];
vector<int> mids[20];
void init(int l, int r, vector<int>& a, int dep = 0) {
if (l == r) return;
int mid = (l+r)/2;
mids[dep].push_back(mid);
lay[dep][mid] = a[mid];
lay[dep][mid+1] = a[mid+1];
for (int i = mid-1; i >= l; i--)
lay[dep][i] = Secret(a[i], lay[dep][i+1]);
for (int i = mid+2; i <= r; i++)
lay[dep][i] = Secret(lay[dep][i-1], a[i]);
init(l, mid, a, dep + 1);
init(mid+1, r, a, dep + 1);
}
void Init(int n, int* a) {
vector<int> _a(n);
for (int i = 0; i < n; i++)
_a[i] = a[i];
init(0, n-1, _a);
}
int Query(int l, int r) {
for (int d = 0;; d++) {
for (int mid : mids[d]) {
if (l <= mid && mid <= r) {
return Secret(lay[d][l], lay[d][r]);
}
}
}
}
