#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> _a;
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) {
for (int i = 0; i < 20; i++)
lay[i].resize(n);
_a.resize(n);
for (int i = 0; i < n; i++)
_a[i] = a[i];
init(0, n-1, _a);
}
int query(int l, int r, int ql, int qr, int dep = 0) {
int mid = (l+r)/2;
if (ql <= mid+1 && mid <= qr) {
if (ql == mid+1)
return lay[dep][qr];
return Secret(lay[dep][ql], lay[dep][qr]);
}
if (qr < mid)
return query(l, mid, ql, qr, dep + 1);
else
return query(mid+1, r, ql, qr, dep + 1);
}
int Query(int l, int r) {
if (l == r) return _a[l];
return query(0, _a.size(), l, r);
}
