（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问题。

试补全程序。

② 处应填（ ）