Touko 最喜欢的数字序列是 $$$1, a_2, \dots, a_n$$$ 的排列 $$$1, 2, \dots, n$$$,她想要一些与她最喜欢的排列类似的排列集合。
她有一个 $$$q$$$ 间隔的集合,其形式为 $$$[l_i, r_i]$$$,其中 $$$1 \le l_i \le r_i \le n$$$。为了创建与她最喜欢的排列类似的排列,她创造了以下定义:
- 排列 $$$b_1, b_2, \dots, b_n$$$ 允许区间 $$$[l', r']$$$ 保持其形状,如果对于任何整数对 $$$(x, y)$$$ 使得 $$$l' \le x < y \le r'$$$,我们有 $$$b_x < b_y$$$ 当且仅当$$$a_x < a_y$$$。
- 如果 $$$b$$$ 允许所有 $$$1 \le i \le k$$$ 的所有区间 $$$[l_i, r_i]$$$ 保持其形状,则排列 $$$b_1, b_2, \dots, b_n$$$ 是 $$$k$$$-相似。
Yuu 想要找出 Touko 的所有 $$$k$$$ 类似排列,但事实证明这是一项非常艰巨的任务;相反,Yuu 将使用有向无环图 (DAG) 对所有 $$$k$$$ 类似排列的集合进行编码。 Yuu 还为自己创造了以下定义:
- 排列 $$$b_1, b_2, \dots, b_n$$$ 满足 DAG $$$G'$$$ 如果对于 $$$G'$$$ 中的所有边 $$$u \to v$$$,我们必须有 $$$b_u < b_v$$$。
- $$$k$$$ 编码是顶点集 $$$1, 2, \dots, n$$$ 上的 DAG $$$G_k$$$,使得排列 $$$b_1, b_2, \dots, b_n$$$ 满足 $$$G_k$$$ 当且仅当 $$$b$$$ 为$$$k$$$-类似。
由于 Yuu 今天有空,她想计算出从 $$$1$$$ 到 $$$q$$$ 的每个 $$$k$$$ 的所有 $$$k$$$ 编码中的最小边数。
输入
第一行包含两个整数 $$$n$$$ 和 $$$q$$$ ($$$1 \le n \le 25\,000$$$, $$$1 \le q \le 100\,000$$$)。
第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \dots, a_n$$$,它们形成 $$$1, 2, \dots, n$$$ 的排列。
以下 $$$q$$$ 行中的第 $$$i$$$ 行包含两个整数 $$$l_i$$$ 和 $$$r_i$$$。 ($$$1 \le l_i \le r_i \le n$$$)。
输出
打印 $$$q$$$ 行。其中第 $$$k$$$ 应包含一个整数 - 所有 $$$k$$$ 编码中边的最小数量。
示例
输入 #1
4 3 2 4 1 3 1 3 2 4 1 4
输出 #1
2 4 3
输入 #2
8 4 3 7 4 8 1 5 2 6 3 6 1 6 3 8 1 8
输出 #2
3 5 9 7
输入 #3
10 10 10 5 1 2 7 3 9 4 6 8 2 2 4 5 6 8 4 10 4 4 2 7 2 2 7 8 3 7 2 10
输出 #3
0 1 3 6 6 9 9 9 9 8
注意
对于第一个测试用例:
- 所有 $$$1$$$ 相似的排列必须允许区间 $$$[1, 3]$$$ 保持其形状。因此,所有$$$1$$$相似排列的集合是$$$\{[3, 4, 2, 1], [3, 4, 1, 2], [2, 4, 1, 3], [2, 3, 1, 4]\}$$$。这些排列的最佳编码是
- 所有 $$$2$$$ 相似排列必须允许区间 $$$[1, 3]$$$ 和 $$$[2, 4]$$$ 保持其形状。因此,所有 $$$2$$$ 相似排列的集合是 $$$\{[3, 4, 1, 2], [2, 4, 1, 3]\}$$$。这些排列的最佳编码是
- 所有 $$$3$$$ 相似排列必须允许区间 $$$[1, 3]$$$、$$$[2, 4]$$$ 和 $$$[1, 4]$$$ 保持其形状。因此,所有 $$$3$$$ 相似排列的集合仅包括 $$$[2, 4, 1, 3]$$$。该排列的最佳编码是