#include <bits/stdc++.h>
using namespace std;
#include "secret.h"
namespace local{
vector<int> v;
struct Node{
int l, r;
vector<int> V;
Node() = default;
Node(int L, int R): l(L), r(R) {
V.resize(r - l + 1);
int m = (l + r) / 2;
V[m - l] = v[m]; V[m - l + 1] = v[m+1];
for (int i = m - l - 1; i >= 0; i--) V[i] = Secret(v[i+l], V[i+1]);
for (int i = m - l + 2; i < r - l + 1; i++) V[i] = Secret(V[i-1], v[i+l]);
}
};
struct Segtree{
vector<Node> tree;
int _n;
Segtree() = default;
Segtree(int N): tree(4*N), _n(N) {
build(1, 0, N-1);
}
void build(int i, int l, int r){
tree[i] = Node(l, r);
if (l == r) return;
int m = (l + r) / 2;
build(i<<1, l, m);
build(i<<1|1, m+1, r);
}
int get(int tl, int tr) { return get(1, 0, _n - 1, tl, tr); }
int get(int i, int l, int r, int tl, int tr){
int m = (l + r) / 2;
if (l == r) return tree[i].V[0];
if (tl <= m && m < tr) return Secret(tree[i].V[tl-l], tree[i].V[tr-l]);
if (tr <= m) return get(i<<1, l, m, tl, tr);
return get(i<<1|1, m+1, r, tl, tr);
}
} st;
}
void Init(int N, int A[]){
local::v.resize(N);
for (int i = 0; i < N; i++) local::v[i] = A[i];
local::st = local::Segtree(N);
}
int Query(int L, int R){
return local::st.get(L, R);
}
