CF1764C.Doremy's City Construction

Doremy's new city is under construction! The city can be regarded as a simple undirected graph with $n$ vertices. The $i$-th vertex has altitude $a_i$. Now Doremy is deciding which pairs of vertices should be connected with edges.

Due to economic reasons, there should be no self-loops or multiple edges in the graph.

Due to safety reasons, there should not be pairwise distinct vertices $u$, $v$, and $w$ such that $a_u \leq a_v \leq a_w$ and the edges $(u,v)$ and $(v,w)$ exist.

Under these constraints, Doremy would like to know the maximum possible number of edges in the graph. Can you help her?

Note that the constructed graph is allowed to be disconnected.

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

出于经济原因，图中不允许存在自环或重边。

出于安全原因，图中不能存在三个互不相同的顶点 $u$、$v$ 和 $w$，使得 $a_u \leq a_v \leq a_w$，且边 $(u,v)$ 与 $(v,w)$ 均存在。

在满足上述约束条件下，Doremy 想知道图中可能的最大边数。你能帮她吗？

注意：所构造的图允许不连通。

The input consists of multiple test cases. The first line contains a single integer $t$ ($1\le t\le 10^4$) — the number of test cases. The description of the test cases follows.

The first line of each test case contains a single integer $n$ ($2 \le n \le 2\cdot 10^5$) — the number of vertices.

The second line of each test case contains $n$ integers $a_1, a_2, \dots, a_n$ ($1\le a_i\le 10^6$) — the altitudes of each vertex.

It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$.

输入包含多个测试用例。第一行包含一个整数 $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$。

For each test case, output the maximum possible number of edges in the graph.

对于每个测试用例，输出图中可能的最大边数。

In the first test case, there can only be at most $3$ edges in the graph. A possible construction is to connect $(1,3)$, $(2,3)$, $(3,4)$. In the picture below the red number above node $i$ is $a_i$.

The following list shows all such $u$, $v$, $w$ that the edges $(u,v)$ and $(v,w)$ exist.

• $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$.

Another possible construction is to connect $(1,4)$, $(2,4)$, $(3,4)$.

An unacceptable construction is to connect $(1,3)$, $(2,3)$, $(2,4)$, $(3,4)$. Because when $u=4$, $v=2$, $w=3$, $a_u\le a_v \le a_w$ holds, and the respective edges exist.

在第一个测试用例中，图中最多只能有 $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$，且对应的边均存在。