题目描述

给定一个长度为 $n$ 的排列 $p_1, p_2, \ldots, p_n$，满足对于所有 $1 \leq i \leq n-2$，都有 $\max(p_i, p_{i+1}) > p_{i+2}$。

计算所有满足 $1 \leq l \leq r \leq n$ 的子数组 $[p_l, p_{l+1}, \ldots, p_r]$ 的最长下降子序列长度之和。

术语说明

• 排列：长度为 $n$ 的排列是由 $1$ 到 $n$ 的所有不同整数任意顺序组成的数组。例如，$[2,3,1,5,4]$ 是排列，但 $[1,2,2]$（有重复元素）和 $[1,3,4]$（包含超出 $n$ 的元素）都不是排列。
• 最长下降子序列（LDS）：对于一个长度为 $m$ 的数组 $b$，最长下降子序列是指满足以下条件的索引序列 $i_1, i_2, \ldots, i_k$：
  1. $1 \leq i_1 < i_2 < \ldots < i_k \leq m$
  2. $b_{i_1} > b_{i_2} > \ldots > b_{i_k}$ 最长下降子序列的长度 $k$ 即为 LDS 的值。

输入格式

第一行包含一个整数 $t$（$1 \leq t \leq 10000$），表示测试用例的数量。

每个测试用例的第一行包含一个整数 $n$（$3 \leq n \leq 500000$）。

第二行包含 $n$ 个整数 $p_1, p_2, \ldots, p_n$（$1 \leq p_i \leq n$，所有 $p_i$ 互不相同）。

保证对于所有测试用例，满足 $\max(p_i, p_{i+1}) > p_{i+2}$（$1 \leq i \leq n-2$）。

所有测试用例的 $n$ 之和不超过 $500000$。

输出格式

对于每个测试用例，输出所有子数组的最长下降子序列长度之和。

样例输入

4
3
3 2 1
4
4 3 1 2
6
6 1 5 2 4 3
3
2 3 1

样例输出

10
17
40
8

提示

对于任意数组 $a$，我们用 $\text{LDS}(a)$ 表示其最长下降子序列的长度。

第一个测试用例中，所有子数组都是严格下降的，因此：

• 长度为 $1$ 的子数组有 $3$ 个，每个的 LDS 为 $1$，总和 $3 \times 1 = 3$；
• 长度为 $2$ 的子数组有 $2$ 个，每个的 LDS 为 $2$，总和 $2 \times 2 = 4$；
• 长度为 $3$ 的子数组有 $1$ 个，LDS 为 $3$，总和 $1 \times 3 = 3$；
• 总答案：$3 + 4 + 3 = 10$。

第二个测试用例的详细计算如下：

• 长度为 $1$ 的子数组：$[4], [3], [1], [2]$，每个 LDS 为 $1$，总和 $4 \times 1 = 4$；
• 长度为 $2$ 的子数组：$[4,3]$（LDS=2）、$[3,1]$（LDS=2）、$[1,2]$（LDS=1），总和 $2 + 2 + 1 = 5$；
• 长度为 $3$ 的子数组：$[4,3,1]$（LDS=3）、$[3,1,2]$（LDS=2），总和 $3 + 2 = 5$；
• 长度为 $4$ 的子数组：$[4,3,1,2]$（LDS=3），总和 $3$；
• 总答案：$4 + 5 + 5 + 3 = 17$。