这是问题的简单版本。两个版本之间的唯一区别是对 $$$y$$$ 的约束。在此版本中$$$y = 0$$$。只有两个版本都解决了,你才能进行黑客攻击。
Bessie 收到了她最好的朋友 Elsie 寄来的生日蛋糕,它是一个正多边形,有 $$$n$$$ 边。蛋糕的顶点顺时针编号为从 $$$1$$$ 到 $$$n$$$。您和贝西将选择其中一些顶点来将不相交的对角线切入蛋糕。换句话说,对角线的端点必须是所选顶点的一部分。
Bessie 只想分发一块蛋糕,形成三角形以保持一致性。块的大小并不重要,整个蛋糕不必分成所有三角形(蛋糕中允许有其他形状,但这些不会被计算在内)。
Bessie 已经选择了 $$$x$$$ 个可用于形成对角线的顶点。她希望你选择不超过 $$$y$$$ 个其他顶点,这样她可以给出的三角形蛋糕的数量就最大化。
贝西最多能给出多少块三角形蛋糕?
输入
第一行包含一个整数 $$$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
3 8 4 0 1 6 2 5 8 8 0 1 3 2 5 4 6 7 8 4 2 0 1 3
输出 #1
2 6 2
注意
在测试用例$$$1$$$、$$$2$$$和$$$3$$$中,分别可以得到$$$2$$$、$$$6$$$和$$$2$$$不相交的三角形蛋糕。下图显示了一种可能的结构:
绿点代表可以使用的顶点,蓝线代表绘制的对角线,红色数字代表计算的三角形。