这是问题的困难版本。两个版本之间的唯一区别是对 $$$y$$$ 的约束。在此版本中 $$$0 \leq y \leq n - x$$$。只有两个版本都解决了,你才能进行黑客攻击。
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)$$$, $$$0 \leq y \leq n - x$$$) — 多边形的边数、Bessie 选择的顶点数以及您可以选择的其他顶点的最大数量。
第二行由 $$$x$$$ 不同的整数组成,从 $$$1$$$ 到 $$$n$$$,代表 Bessie 选择的顶点。
保证所有测试用例的 $$$x$$$ 总和不超过 $$$2 \cdot 10^5$$$。
输出
对于每个测试用例,输出一个整数:她可以给出的不相交三角形蛋糕的最大数量。
示例
输入 #1
3 8 4 2 1 6 2 5 7 3 1 6 4 3 4 2 2 1 3
输出 #1
6 5 2
注意
在测试用例 $$$1$$$、$$$2$$$ 和 $$$3$$$ 中,分别可以得到 $$$6$$$、$$$5$$$ 和 $$$2$$$ 不相交的三角形蛋糕。下图显示了一种可能的结构:
绿点代表 Bessie 选择的顶点,黄点代表您选择的顶点,蓝线代表绘制的对角线,红色数字代表计算的三角形。