← 返回题目列表

Codeforces · 1764/C

C. 多雷米的城市建设

中文机器翻译题面 查看原题

多米的新城正在建设中!城市可以被视为具有 $$$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$$$成立,且各自的边存在。