解题思路

给定数组 $a_1,a_2,\ldots,a_n$。对任意区间 $[l,r]$ $(1\le l<r\le n)$，其贡献定义为区间内部所有下标 $i$（$l<i<r$）中满足

的个数。要求所有区间贡献之和。

题目内容

给定一个长度为 $n$ 的整数数组 {$a_1,a_2,...,a_n$}。对任意区间 $[l,r]$ (满足 $1 ≤l<r≤n$ )，定义其贡献为所有满足 $l<i<r$ 且 $(a_i< a_l)$ 或 $(a_i< a_r)$ 的下标 $i$ 的个数。请你计算所有区间的贡献之和。

输入描述

每个测试文件均包含多组测试数据。第一行输入一个整数 $T(1≤T≤2×10^5)$ 代表数据组数。

每组测试数据描述如下：

• 第一行输入一个整数 $n(1≤n≤2×10^5)$ ，表示数组的长度；

• 第二行输入 $n$ 个整数 $a_1,a_2,...,a_n(1≦a_i≦10^9)$ ，表示数组的元素。

除此之外，保证单个测试文件的 $n$ 之和不超过 $2×10^5$ 。

输出描述

对于每组测试数据，新起一行输出一个整数，表示答案。

样例1

输入

2
3
2 1 3
4
3 2 2 3

输出

1
4

说明

对第一组数据：$n=3,a=$ {$2,1,3$}。

• 区间 $[1,3]$ 的内部仅有 $i=2$ ，有 $a_2=1＜a_1=2$ ，因此该区间贡献为 $1$；

• 其余区间内部为空，贡献为 $0$ ；

• 总贡献为 $1$ 。