哆蕾咪的新城市正在建设中！这个城市可以被看作一个含有 $n$ 个顶点的简单无向图。第 $i$ 个顶点的海拔高度为 $a_i$。现在哆蕾咪正在决定应该在哪些顶点对之间连接边。

由于经济原因，图中不应存在自环或重边。

由于安全原因，图中不应存在两两不同的顶点 $u$、$v$ 和 $w$，使得 $a_u \le a_v \le a_w$ 且边 $(u, v)$ 和 $(v, w)$ 同时存在。

在这些限制条件下，哆蕾咪想知道图中最多可以有多少条边。你能帮帮她吗？

请注意，构建的图允许是不连通的。

输入格式

输入由多个测试用例组成。第一行包含一个整数 $t$ ($1 \le t \le 10^4$) — 测试用例的数量。接下来是每个测试用例的描述。

每个测试用例的第一行包含一个整数 $n$ ($2 \le n \le 2 \cdot 10^5$) — 顶点的数量。

每个测试用例的第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 10^6$) — 每个顶点的海拔高度。

保证所有测试用例中 $n$ 的总和不超过 $2 \cdot 10^5$。

输出格式

对于每个测试用例，输出图中最多可以有的边数。

样例

输入样例 1

4
4
2 2 3 1
6
5 2 3 1 5 2
12
7 2 4 9 1 4 6 3 7 4 2 3
4
1000000 1000000 1000000 1000000

输出样例 1

3
9
35
2

说明

在第一个测试用例中，图中最多只能有 $3$ 条边。一种可能的构建方式是连接 $(1, 3)$、$(2, 3)$、$(3, 4)$。在下图中，节点 $i$ 上方的红色数字是 $a_i$。

以下列表显示了所有满足边 $(u, v)$ 和 $(v, w)$ 同时存在的 $u, v, w$：

• $u = 1, v = 3, w = 2$;
• $u = 1, v = 3, w = 4$;
• $u = 2, v = 3, w = 1$;
• $u = 2, v = 3, w = 4$;
• $u = 4, v = 3, w = 1$;
• $u = 4, v = 3, w = 2$.

另一种可能的构建方式是连接 $(1, 4)$、$(2, 4)$、$(3, 4)$。

一种不可行的构建方式是连接 $(1, 3)$、$(2, 3)$、$(2, 4)$、$(3, 4)$。因为当 $u = 4, v = 2, w = 3$ 时，$a_u \le a_v \le a_w$ 成立，且对应的边均存在。