题目描述

定义$(i,j)(i \lt j)$ 为合法的二元组满足以下两个条件：

• $a_j \gt a_i$
• 不存在$k$ 满足$i \lt k \lt j$ 且$(a_k \gt a_i)$ .

给出一个数组$a$，求出在所有的子串中，合法二元组的数量

说明：这里的子串指连续子数组。例如：在数组[1,2,3]中，[1],[1,2],[2,3],[1,2,3]...是子串，而[1,3]不是，因为其在原数组中不连续。

输入格式

第一行输入一个正整数$t$，表示一共有$t$个测试样例$(1 \le t \le 10^5)$

对于每个测试样例

第一行是一个正整数$n(1 \le n \le 2*10^5)$，表示数组的$a$长度

第二行是$n$个正整数$a_i(1 \le a_i \le 10^9)$，表示数组的第$i$个数字 数组保证$\sum |n| \le 2*10^5$

输出格式

输出一个正整数，代表在所有字串中，合法二元组的数量。

样例

3
2
1 2
3
2 1 3
3
1 2 3

1
3
4

#说明

样例1

对于子串1 2,因为1 $\lt$ 2并且不存在k 满足 $1 \lt k \lt 1$，所以有一个合法的二元组(1,2)

样例2

对于子串1 3,同上，有一个合法的二元组(1,2)

对于子串2 1 3,合法的二元组有(1,3)(2,3)

所以总共有3个合法的二元组

样例3

对于子串1 2,有一个合法二元组(1,2)

对于子串2 3,有一个合法二元组(1,2)

对于子串1 2 3,有合法二元组(1,2)(2,3)

所以总共有4个合法的二元组