（RMQ 区间最值问题）给定序列a0,⋯,an-1，和

（RMQ 区间最值问题）给定序列a0,⋯,an-1，和m次询问，每次询问给定l,r，求max{al,⋯,ar}。

为了解决该问题，有一个算法叫the Method of Four Russians，其时间复杂度为O(n+m)，步骤如下：

1) 建立Cartesian（笛卡尔）树，将问题转化为树上的LCA（最近公共祖先）问题。
2) 对于LCA问题，可以考虑其Euler序（即按照DFS过程，经过所有点，环游回根的序列），即求Euler序列上两点间一个新的RMQ问题。
3) 注意新的问题为±1 RMQ，即相邻两点的深度差一定为1。

下面解决这个±1 RMQ问题，“序列”指Euler序列：

1) 设t为Euler序列长度。取。将序列每b个分为一大块，使用ST表（倍增表）处理大块间的RMQ问题，复杂度。
2)（重点）对于一个块内的RMQ问题，也需要O(1)的算法。由于差分数组2b−1种，可以预处理出所有情况下的最值位置，预处理复杂度O(b2b)，不超过O(n)。
3) 最终，对于一个查询，可以转化为中间整的大块的RMQ问题，以及两端块内的RMQ问题。

试补全程序。

#include <iostream>
#include <cmath>
using namespace std;
const int MAXN = 100000, MAXT = MAXN << 1;
const int MAXL = 18, MAXB = 9, MAXC = MAXT / MAXB;
struct node {
    int val;
    int dep, dfn, end;
    node *son[2]; // son[0], son[1] 分别表示左右儿子
} T[MAXN];
int n, t, b, c, Log2[MAXC + 1];
int Pos[(1 << (MAXB - 1)) + 5], Dif[MAXC + 1];
node *root, *A[MAXT], *Min[MAXL][MAXC];
void build() { // 建立 Cartesian 树
    static node *S[MAXN + 1];
    int top = 0;
    for (int i = 0; i < n; i++) {
        node *p = &T[i];
        while (top && S[top]->val < p->val)
            ①;
        if (top)
            ②;
        S[++top] = p;
    }
    root = S[1];
}
void DFS(node *p) { // 构建 Euler 序列
    A[p->dfn = t++] = p;
    for (int i = 0; i < 2; i++)
        if (p->son[i]) {
            p->son[i]->dep = p->dep + 1;
            DFS(p->son[i]);        
            A[t++] = p;        
        }            
        p->end    = t - 1;        
}
node *min(node *x, node *y) {
    return ③ ? x : y;
}
void ST_init() {
    b = (int)(ceil(log2(t) / 2));
    c = t / b;
    Log2[1] = 0;
    for (int i = 2; i <= c; i++)
        Log2[i] = Log2[i >> 1] + 1;
    for (int i = 0; i < c; i++) {
        Min[0][i] = A[i * b];
        for (int j = 1; j < b; j++)
            Min[0][i] = min(Min[0][i], A[i * b + j]);
    }
    for (int i = 1, l = 2; l <= c; i++, l <<= 1)
        for (int j = 0; j + l <= c; j++)
            Min[i][j] = min(Min[i - 1][j], Min[i - 1][j + (l >> 1)]);
}
void small_init() { // 块内预处理
    for (int i = 0; i <= c; i++)
    for (int j = 1; j < b && i * b + j < t; j++)
        if (④)
            Dif[i] |= 1 << (j - 1);
    for (int S = 0; S < (1 << (b - 1)); S++) {
        int mx = 0, v = 0;
        for (int i = 1; i < b; i++) {
            ⑤;
            if (v < mx) {
                mx = v;
                Pos[S] = i;
            }
        }
    }
}
node *ST_query(int l, int r) {
    int g = Log2[r - l + 1];
    return min(Min[g][l], Min[g][r - (1 << g) + 1]);
}
node *small_query(int l, int r) { // 块内查询
    int p = l / b;
    int S = ⑥;
    return A[l + Pos[S]];
}
node *query(int l, int r) {
    if (l > r)
        return query(r, l);
    int pl = l / b, pr = r / b;
    if (pl == pr) {
        return small_query(l, r);
    } else {
        node *s = min(small_query(l, pl * b + b - 1), small_query(pr * b, r));
        if (pl + 1 <= pr - 1)
            s = min(s, ST_query(pl + 1, pr - 1));
        return s;
    }
}
int main() {
    int m;
    cin >> n >> m;
    for (int i = 0; i < n; i++)
        cin >> T[i].val;
    build();
    DFS(root);
    ST_init();
    small_init();
    while (m--) {
        int l, r;
        cin >> l >> r;
        cout << query(T[l].dfn, T[r].dfn)->val << endl;
    }
    return 0;
}

⑥ 处应填（ ）