#include "floppy.h"
#include<bits/stdc++.h>
#pragma GCC optimize("unroll-loops,O3")
using namespace std;
using i64 = long long;
//#define int i64
#define vi vector<int>
#define vvi vector<vi>
#define vb vector<bool>
#define se second
#define fi first
#define pii pair<int, int>
#define sz(x) (int)(x).size()
const int LG = 20;
template <typename T> struct SparseTableMax{
vector<vector<T>> st;
SparseTableMax(const vector<T> &a){
int n = sz(a), lg = __lg(n) + 1;
st.resize(lg);
st[0] = a;
for(int bit = 1; bit < lg; bit++){
st[bit].resize(n - (1 << bit) + 1);
for(int v = 0; v + (1 << bit) - 1 < n; v++){
st[bit][v] = max(st[bit - 1][v], st[bit - 1][v + (1 << (bit - 1))]);
}
}
}
inline T query(int l, int r){
int lg = __lg(r - l + 1);
return max(st[lg][l], st[lg][r - (1 << lg) + 1]);
}
};
template <typename T> struct SparseTableMin{
vector<vector<T>> st;
SparseTableMin(const vector<T> &a){
int n = sz(a), lg = __lg(n) + 1;
st.resize(lg);
st[0] = a;
for(int bit = 1; bit < lg; bit++){
st[bit].resize(n - (1 << bit) + 1);
for(int v = 0; v + (1 << bit) - 1 < n; v++){
st[bit][v] = min(st[bit - 1][v], st[bit - 1][v + (1 << (bit - 1))]);
}
}
}
inline T query(int l, int r){
int lg = __lg(r - l + 1);
return min(st[lg][l], st[lg][r - (1 << lg) + 1]);
}
};
// cartesian tree : (sol_subtree)sağ_subtree
void read_array(int sid, const vi &vec){
vector<pii> temp(sz(vec));
for(int i = 0; i < sz(vec); i++){
temp[i] = {vec[i], i};
}
SparseTableMax<pii> st(temp);
string msg = "";
function<void(int, int)> build_tree = [&](int le, int ri) -> void {
if(le > ri || le < 0 || ri >= sz(temp)) return;
int idx = st.query(le, ri).se;
msg += '0'; // (
if(idx > le) build_tree(le, idx - 1); // sol_subtree
msg += '1'; // )
if(idx < ri) build_tree(idx + 1, ri); // sağ subtree
return;
};
build_tree(0, sz(temp) - 1);
save_to_floppy(msg);
return;
}
vi solve_queries(int sid, int n, const string &msg, const vi &left, const vi &right){
vvi adj(n);
vi close(sz(msg));
stack<int> s;
for(int i = 0; i < sz(msg); i++){
if(msg[i] == '1'){
close[s.top()] = i;
s.pop();
}
else{
s.emplace(i);
}
}
int timer = 0, root = 0; // dfs-order, (sol)sağ diye gittiğim için benim aynı şekilde geri çözünce dfs-order'ım array indeximle aynı oluyor
function<int(int, int)> deconstruct = [&](int le, int ri) -> int {
int lefst = -1, rigst = -1, go = close[le];
if(le + 1 <= go - 1){
lefst = deconstruct(le + 1, go - 1);
}
int myidx = timer++;
if(le == 0 && ri == sz(msg) - 1){
root = myidx;
}
if(lefst != -1){
adj[myidx].emplace_back(lefst);
}
if(go + 1 <= ri){
rigst = deconstruct(go + 1, ri);
adj[myidx].emplace_back(rigst);
}
return myidx;
};
deconstruct(0, sz(msg) - 1);
vi dep(n), tin(n);
vector<pii> t2v(2 * n);
timer = 0;
vvi lift(n, vi(LG));
function<void(int, int)> dfs = [&](int v, int p) -> void {
tin[v] = timer;
t2v[timer++] = {dep[v], v};
/*lift[v][0] = p;
for(int bit = 1; bit < LG; bit++){
lift[v][bit] = lift[lift[v][bit - 1]][bit - 1];
}*/
for(int &u : adj[v]){
dep[u] = dep[v] + 1;
dfs(u, v);
t2v[timer++] = {dep[v], v};
}
return;
};
dfs(root, root);
SparseTableMin<pii> st(t2v);
auto query = [&](int l, int r) -> int {
if(tin[l] > tin[r]) swap(l, r);
return st.query(tin[l], tin[r]).se;
};
auto kth = [&](int a, int k) -> int {
for(int bit = LG - 1; bit >= 0; bit--){
if((k >> bit) & 1){
a = lift[a][bit];
}
}
return a;
};
auto find_lca = [&](int a, int b) -> int {
if(dep[a] < dep[b]) swap(a, b);
a = kth(a, dep[a] - dep[b]);
if(a == b) return a;
for(int bit = LG - 1; bit >= 0; bit--){
if(lift[a][bit] != lift[b][bit]){
a = lift[a][bit];
b = lift[b][bit];
}
}
return lift[a][0];
};
vi ans(sz(left));
for(int i = 0; i < sz(left); i++){
ans[i] = query(left[i], right[i]);
//ans[i] = find_lca(left[i], right[i]);
}
return ans;
}
/*
inline void solve(){
int n, q;
cin >> n >> q;
vi a(n), ql(q), qr(q);
for(int i = 0; i < n; i++){
cin >> a[i];
}
for(int i = 0; i < q; i++){
cin >> ql[i] >> qr[i];
}
read_array(-1, a);
vi res = solve_queries(-1, n, msg, ql, qr);
for(int i = 0; i < sz(res); i++){
cout << res[i] << " ";
}
cout << "\n";
return;
}
signed main(){
ios_base::sync_with_stdio(false); cin.tie(0);
int t = 1;
//cin >> t;
while(t--){
solve();
}
return 0;
}
*/
