#include "secret.h"
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define int long long
using namespace std;
using namespace __gnu_pbds;
using ordered_set = tree <int, null_type, less_equal <int>, rb_tree_tag, tree_order_statistics_node_update>;
ostream &operator <<(ostream &out, vector <int> val) {
for (auto v : val) {
out << v << ' ';
}
return out;
}
vector <int> val;
int n;
class segment_tree {
vector <vector <int>> prev;
vector <vector <int>> suf;
int n;
void build(int num, int l, int r) {
if (r - l <= 2) {
return;
}
int med = (l + r) / 2;
int cur = val[med];
prev[num].push_back(val[med]);
for (int j = med + 1; j < r; ++j) {
prev[num].push_back(Secret(cur, val[j]));
cur = prev[num].back();
}
cur = val[med - 1];
suf[num].push_back(cur);
for (int j = med - 2; j >= l; --j) {
suf[num].push_back(Secret(val[j], cur));
cur = suf[num].back();
}
build(2 * num + 1, l, med);
build(2 * num + 2, med, r);
}
int get(int num, int l, int r, int low, int high) {
int med = (l + r) / 2;
if (med >= low && med < high) {
// cout << l << " " << r << " " << med << " " << low << " " << high << '\n';
int k1 = high - med - 1;
int k2 = med - low - 1;
// cout << k1 << " " << k2 << '\n';
if (k2 >= 0) {
return Secret(suf[num][k2], prev[num][k1]);
} else {
return prev[num][k1];
}
}
if (med >= high) {
return get(2 * num + 1, l, med, low, high);
} else {
return get(2 * num + 2, med, r, low, high);
}
}
public:
int get(int l, int r) {
if (r - l == 1) {
return val[l];
} else if (r - l == 2) {
return Secret(val[l], val[l + 1]);
} else {
return get(0, 0, n, l, r);
}
}
void init(int nn) {
n = nn;
prev.resize(4 * n);
suf.resize(4 * n);
build(0, 0, n);
}
};
segment_tree now;
void Init(int nn, int A[]) {
n = nn;
val.resize(n);
for (int i = 0; i < n; ++i) {
val[i] = A[i];
}
now.init(n);
}
int Query(int l, int r) {
++r;
return now.get(l, r);
}
