每次测试时间限制：$2$ 秒
内存限制：$256$ 兆字节
题目描述 你被给定一个排列 $^{∗}$ $p_1, \ldots, p_n$，且满足对于所有 $1 \leq i \leq n-2$ 都有 $\max(p_i, p_{i+1}) > p_{i+2}$。

计算所有子数组 $[p_l, p_{l+1}, \ldots, p_r]$ 的最长递减子序列 $^{†}$ 的长度之和，其中 $1 \le l \le r \le n$。

$^{∗}$ 长度为 $n$ 的排列是由 $n$ 个互不相同的整数 $1$ 到 $n$ 按任意顺序组成的数组。例如 $[2,3,1,5,4]$ 是一个排列，但 $[1,2,2]$ 不是（$2$ 出现两次），$[1,3,4]$ 也不是（$n=3$ 但数组中有 $4$）。

$^{†}$ 给定一个大小为 $|b|$ 的数组 $b$，一个长度为 $k$ 的递减子序列是指一组下标 $i_1, \ldots, i_k$ 满足：

• $1 \le i_1 < i_2 < \ldots < i_k \le |b|$
• $b_{i_1} > b_{i_2} > \ldots > b_{i_k}$

输入
每个测试点包含多个测试用例。第一行包含一个整数 $t$（$1 \le t \le 10\,000$）——测试用例的数量。
每个测试用例的第一行包含一个整数 $n$（$3 \le n \le 500\,000$）。
第二行包含 $n$ 个整数 $p_1, p_2, \ldots, p_n$（$1 \le p_i \le n$，$p_i$ 两两不同）。
保证对于所有 $1 \le i \le n-2$ 有 $\max(p_i, p_{i+1}) > p_{i+2}$。
所有测试用例的 $n$ 之和不超过 $500\,000$。

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

示例
输入

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)$ 为 $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$。