题目内容

在一维频谱分析中，工程师记录了一串长度为 $n$ 的频点的能量值 $a_1, a_2, \dots, a_n$。对于每一个出现过的能量值 $v$，将它在序列中出现的位置按从小到大排列为 $p_1 < p_2 < \dots < p_m$。我们将相邻两个位置 $(p_k, p_{k+1})$ 称为 $v$ 的一个「同频紧邻对」。

对于同频紧邻对 $(l, r)$，定义其「低值干扰数」为区间 $[l, r]$ 内能量值严格小于 $v$ 的频点个数。请你计算出所有同频紧邻对的低值干扰数之和。

约束条件：

• 测试数据组数 T 不超过 10^4。
• 每组数据的频点数量 n 不超过 2×10^5。
• 每个能量值 $a_i$ 是介于 1 到 n 之间的整数。
• 所有测试数据的 n 总和不超过 2×10^5。

输入描述

第一行包含一个整数 T，表示测试数据组数。之后每组数据按以下格式给出： 第一行一个整数 n，表示频点数量； 第二行包含 n 个整数 $a_1, a_2, \dots, a_n$，表示各频点的能量值。

数据范围已在题目描述中说明。

输出描述

对于每组测试数据，输出一行一个整数，表示该组数据中所有同频紧邻对的低值干扰数之和。

样例1

输入

1
3
1 2 3

输出

0

说明

数组为 [1, 2, 3]，每个能量值均仅出现 1 次，没有任何「同频紧邻对」，所以低值干扰数之和为 0。

样例2

输入

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

输出

1
1

说明

第一组数据： 数组 [2, 1, 2, 2]：

• 值 1 出现位置 [2]，没有同频紧邻对。
• 值 2 出现位置 [1, 3, 4]。相邻对 $(1, 3)$：区间 $[1, 3]$ 内包含 [2, 1, 2]，严格小于 2 的只有值 1（位于位置 2），计数为 1。相邻对 $(3, 4)$：区间 $[3, 4]$ 内为 [2, 2]，没有小于 2 的值，计数为 0。 值 2 的总贡献为 1。 因此第一组答案为 1。

第二组数据： 数组 [1, 2, 1, 3, 2, 1]：

• 值 1 位置 [1, 3, 6]，对 $(1,3)$ 和 $(3,6)$。由于 1 是最小值，这些区间内不存在严格小于 1 的元素，贡献均为 0。
• 值 2 位置 [2, 5]，对 $(2,5)$：区间 $[2,5]$ 包含 [2, 1, 3, 2]，严格小于 2 的是位置 3 的值 1，贡献 1。
• 值 3 位置 [4]，无对。 总和为 1。

输出两行分别为 1 和 1。

样例3

输入

1
5
3 1 2 1 3

输出

3

说明

数组 [3, 1, 2, 1, 3]：

• 值 1 位置 [2, 4]，对 $(2,4)$：区间 $[2,4]$ 为 [1, 2, 1]，无小于 1 的元素，贡献 0。
• 值 2 位置 [3]，无对。
• 值 3 位置 [1, 5]，对 $(1,5)$：区间 $[1,5]$ 包含整个数组 [3, 1, 2, 1, 3]，其中严格小于 3 的元素有位置 2 的 1、位置 3 的 2、位置 4 的 1，共 3 个，贡献 3。 总和为 3。