多米的新城正在建设中!城市可以被视为具有 $$$n$$$ 个顶点的简单无向图。第 $$$i$$$ 个顶点的高度为 $$$a_i$$$。现在 Doremy 正在决定哪些顶点对应该用边连接。
由于经济原因,图中不应存在自环或多边。
出于安全原因,不应存在成对不同的顶点 $$$u$$$、$$$v$$$ 和 $$$w$$$ 使得 $$$a_u \leq a_v \leq a_w$$$ 以及边 $$$(u,v)$$$ 和 $$$(v,w)$$$ 存在。
在这些约束下,Doremy 想知道图中边的最大可能数量。你能帮助她吗?
注意构造的图是允许断开的。
输入
输入由多个测试用例组成。第一行包含一个整数 $$$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$$$成立,且各自的边存在。