#include "secret.h"
#include <vector>
#include <map>
#include <utility>
#include <algorithm>
std::map<std::pair<int, int>, int> secret_map;
int mySecret(int X, int Y) {
if(X == -2) return Y;
if(Y == -2) return X;
if(X == -1 || Y == -1) {
return -1;
}
if(secret_map.find({X, Y}) != secret_map.end()) {
return secret_map[{X, Y}];
}
return secret_map[{X, Y}] = Secret(X, Y);
}
struct SegTree {
int offset;
std::vector<int> tree;
SegTree(int n, int a[]) {
offset = 1;
while (offset <= n) {
offset *= 2;
}
tree.resize(2 * offset, -1);
for(int i = 0; i < n; i++) {
tree[offset + i] = a[i];
}
for(int i = offset - 1; i >= 1; i--) {
tree[i] = mySecret(tree[2 * i], tree[2 * i + 1]);
}
}
int _query(int node, int l, int r, int gl, int gr) {
if (gl > r || gr < l) {
return -2;
}
if (gl <= l && gr >= r) {
return tree[node];
}
int mid = (l + r) / 2;
return mySecret(_query(node * 2, l, mid, gl, gr), _query(node * 2 + 1, mid + 1, r, gl, gr));
}
int query(int l, int r) {
return _query(1, 0, offset - 1, l, r);
}
} st(0, nullptr);
void Init(int N, int A[]) {
// int *ptr = new int[N];
// ptr[i] <=> *(ptr + i);
// i[ptr] = ptr[i] daca i = int, ptr = int*
// ptr[i] = *(ptr + i) = *(i + ptr) = i[ptr]
st = SegTree(N, A);
}
int Query(int L, int R) {
return st.query(L, R);
}
