该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目背景

定义$(i,j)(i \lt j)$ 为合法的二元组当且仅当$a_j \gt a_i$ 且 不存在$k$ 满足$i \lt k \lt j$ 且$(a_k \gt a_i)$ .

给出一个数组$a$，求数组中合法二元组的数量

输入格式

第一行输入一个正整数$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$个数字

输出格式

输出一个正整数，代表合法二元组的数量。

样例

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

1
2
2

#说明

样例1

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

样例2

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

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

样例3

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

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