CF1942C1.Bessie's Birthday Cake (Easy Version)

Proof Geometric Construction Can Solve All Love Affairs - manbo-p

⠀

这是该问题的简单版本。两个版本的唯一区别在于 $y$ 的限制。在本版本中，$y = 0$。只有当两个版本都被解决时，你才能进行 hack。

Bessie 收到了她最好的朋友 Elsie 送来的生日蛋糕，这个蛋糕是一个有 $n$ 条边的正多边形。蛋糕的顶点按顺时针方向从 $1$ 到 $n$ 编号。你和 Bessie 将选择其中一些顶点，在蛋糕上切出不相交的对角线。换句话说，对角线的两个端点必须是被选中的顶点。

Bessie 只想分发那些能形成三角形的蛋糕块以保持一致性。蛋糕块的大小无关紧要，整个蛋糕不必全部被分成三角形（蛋糕中可以有其他形状，但这些不会被计数）。

Bessie 已经选好了 $x$ 个可以用来画对角线的顶点。她希望你最多再选择 $y$ 个顶点，使她能分发的三角形蛋糕块数量最大化。

Bessie 能分发的三角形蛋糕块的最大数量是多少？

第一行包含一个整数 $t$（$1 \leq t \leq 10^4$），表示测试用例的数量。

每个测试用例的第一行包含三个整数 $n$、$x$ 和 $y$（$4 \leq n \leq 10^9$，$2 \leq x \leq \min(n, 2 \cdot 10^5)$，$y = 0$），分别表示多边形的边数、Bessie 已经选好的顶点数，以及你最多还能选择的顶点数。

第二行包含 $x$ 个互不相同的整数，范围从 $1$ 到 $n$，表示 Bessie 已经选好的顶点。

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

对于每个测试用例，输出一个整数，表示她能分发的最大不相交三角形蛋糕块数量。

在第 $1$、$2$ 和 $3$ 个测试用例中，你分别可以获得 $2$、$6$ 和 $2$ 个不相交的三角形蛋糕块。如下图所示为一种可能的构造方式：

绿色的点表示可以使用的顶点，蓝色的线表示已经画出的对角线，红色的数字表示被计数的三角形。

由 ChatGPT 4.1 翻译