给你一个排列$$$^{\text{*}}$$$ $$$p_1, \ldots, p_n$$$,使得$$$\max(p_i, p_{i+1}) \gt p_{i+2}$$$对于所有$$$1 \leq i \leq n-2$$$。
计算所有对 $$$1 \leq l \leq r \leq n$$$ 子数组 $$$[p_l, p_{l+1}, \ldots, p_r]$$$ 的最长递减子序列$$$^{\text{†}}$$$ 的长度之和。
$$$^{\text{*}}$$$长度$$$n$$$的排列是一个由从$$$1$$$到$$$n$$$以任意顺序的$$$n$$$个不同整数组成的数组。例如,$$$[2,3,1,5,4]$$$是一个排列,但$$$[1,2,2]$$$不是排列($$$2$$$在数组中出现两次),$$$[1,3,4]$$$也不是排列($$$n=3$$$但数组中有$$$4$$$)。
$$$^{\text{†}}$$$给定一个大小为 $$$|b|$$$ 的数组 $$$b$$$,长度 $$$k$$$ 的递减子序列是索引 $$$i_1, \ldots, i_k$$$ 的序列,使得:
- $$$1 \leq i_1 \lt i_2 \lt \ldots \lt i_k \leq |b|$$$
- $$$b_{i_1} \gt b_{i_2} \gt \ldots \gt b_{i_k}$$$
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10\,000$$$)。测试用例的描述如下。
每个测试用例的第一行包含一个整数 $$$n$$$ ($$$3 \leq n \leq 500\,000$$$)。
每个测试用例的第二行包含 $$$n$$$ 整数 $$$p_1, p_2, \ldots, p_n$$$ ($$$1 \le p_i \le n$$$, $$$p_i$$$ 成对不同)。
保证 $$$\max(p_i, p_{i+1}) \gt p_{i+2}$$$ 对于所有 $$$1 \leq i \leq n-2$$$。
所有测试用例的 $$$n$$$ 总和不超过 $$$500\,000$$$。
输出
对于每个测试用例,输出其最长递减子序列长度的所有子数组的总和。
示例
输入复制
433 2 144 3 1 266 1 5 2 4 332 3 1
输出复制
10 17 40 8
注意
对于任何数组 $$$a$$$,我们将 $$$\text{LDS}(a)$$$ 定义为 $$$a$$$ 的最长递减子序列的长度。
在第一个测试用例中,所有子数组都在减少。
在第二个中,我们有
$$$\text{LDS}([4]) = \text{LDS}([3]) = \text{LDS}([1]) = \text{LDS}([2]) = 1$$$
$$$\text{LDS}([4,3]) = \text{LDS}([3,1]) = 2, \text{LDS}([1, 2]) = 1$$$
$$$\text{LDS}([4,3,1]) = 3, \text{LDS}([3,1,2]) = 2$$$
$$$\text{LDS}([4,3,1,2]) = 3$$$
所以答案是$$$1+1+1+1+2+2+1+3+2+3=17$$$。