对于长度为 $$$m$$$ 的数组 $$$b$$$,定义 $$$f(b)$$$ 如下:
- 考虑长度为 $$$m$$$ 的数组 $$$c$$$ 美丽 当且仅当对于每个 $$$1 \le i \le m$$$,$$$c_i$$$ 等于 $$$\max(b_1,b_2,\ldots,b_i)$$$ 或 $$$\min(b_1,b_2,\ldots,b_i)$$$。然后,$$$f(b)$$$ 被定义为所有漂亮数组上的最大反转次数$$$^{\text{*}}$$$。
给你一个排列$$$^{\text{†}}$$$ $$$p$$$,长度为$$$n$$$。您需要回答 $$$q$$$ 查询,其中每个查询包含两个整数 $$$l$$$ 和 $$$r$$$ ($$$1 \le l \le r \le n$$$)。对于每个查询,请计算 $$$f([p_l,p_{l+1},\ldots,p_{r}])$$$。
$$$^{\text{*}}$$$长度为$$$n$$$的数组$$$a$$$的反转次数被定义为整数对$$$(i,j)$$$的数量,使得$$$1 \le i \lt j \le n$$$和$$$a_i \gt a_j$$$。
$$$^{\text{†}}$$$长度$$$n$$$的排列是一个由从$$$1$$$到$$$n$$$以任意顺序的$$$n$$$不同整数组成的数组。例如,$$$[2,3,1,5,4]$$$是一个排列,但$$$[1,2,2]$$$不是排列($$$2$$$在数组中出现两次),$$$[1,3,4]$$$也不是排列($$$n=3$$$但数组中有$$$4$$$)。
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^4$$$)。测试用例的描述如下。
每个测试用例的第一行包含两个整数$$$n$$$和$$$q$$$ ($$$1 \le n,q \le 10^6$$$),分别代表$$$p$$$的长度和查询的数量。
第二行包含 $$$n$$$ 不同的整数 $$$p_1,p_2,\ldots,p_n$$$ ($$$1 \le p_i \le n$$$),表示排列 $$$p$$$。
接下来的 $$$q$$$ 行包含两个整数 $$$l$$$ 和 $$$r$$$ ($$$1 \le l \le r \le n$$$),表示一个查询。
保证所有测试用例的$$$n$$$总和和$$$q$$$总和不超过$$$10^6$$$。
输出
对于每个测试用例,输出 $$$q$$$ 个整数,其中第 $$$i$$$ 个整数表示第 $$$i$$$ 个查询的答案。
示例
输入复制
42 21 21 11 22 12 11 25 21 2 3 4 51 42 510 67 10 5 2 8 3 6 4 9 11 61 106 95 102 86 7
输出复制
001221131211130
注意
在第一个示例测试用例中:
- 对于第二个查询,子数组是 $$$[1,2]$$$。您可以采用 $$$c=[\min(1),\min(1,2)]=[1,1]$$$,其中有 $$$0$$$ 反转。可以证明,这是您可以在所有漂亮数组上获得的最大反转次数。
在第四个示例测试用例中:
- 对于第三个查询,子数组为 $$$[3,6,4,9]$$$。您可以采用 $$$c=[\max(3),\max(3,6),\min(3,6,4),\min(3,6,4,9)]=[3,6,3,3]$$$,这将给出总共 $$$2$$$ 的反转。可以证明,这是您可以在所有漂亮数组上获得的最大反转次数。