← 返回题目列表

Codeforces · 1463/D

D. 对

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

你有 $$$2n$$$ 个整数 $$$1, 2, \dots, 2n$$$。您必须将这些 $$$2n$$$ 元素重新分配为 $$$n$$$ 对。之后,您选择 $$$x$$$ 对并从中获取最小元素,并从其他 $$$n - x$$$ 对中获取最大元素。

您的目标是获得数字集 $$$\{b_1, b_2, \dots, b_n\}$$$ 作为从对中获取元素的结果。

不同的 $$$x$$$-s ($$$0 \le x \le n$$$) 的数量是多少,如果对于每个 $$$x$$$ 您可以选择如何将数字分配到对中,并且从哪些 $$$x$$$ 对中选择最小元素,那么可以获得集合 $$$b$$$?

输入

第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 1000$$$) — 测试用例的数量。

每个测试用例的第一行包含整数 $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$)。

每个测试用例的第二行包含 $$$n$$$ 整数 $$$b_1, b_2, \dots, b_n$$$ ($$$1 \le b_1 < b_2 < \dots < b_n \le 2n$$$) - 您想要获得的集合。

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

输出

对于每个测试用例,打印一个数字 - 不同 $$$x$$$-s 的数量,以便可以获得集合 $$$b$$$。

示例

输入 #1

3
1
1
5
1 4 5 9 10
2
3 4

输出 #1

1
3
1

注意

在第一个测试用例中, $$$x = 1$$$ 是唯一的选项:您有一对 $$$(1, 2)$$$ 并从该对中选择最小值。

在第二个测试用例中,存在三种可能的 $$$x$$$-s。如果 $$$x = 1$$$,则可以组成以下对:$$$(1, 6)$$$、$$$(2, 4)$$$、$$$(3, 5)$$$、$$$(7, 9)$$$、$$$(8, 10)$$$。您可以从 $$$(1, 6)$$$ 中获取最小值(等于 $$$1$$$),并从所有其他对中获取最大元素来设置 $$$b$$$。

如果 $$$x = 2$$$,则可以形成对 $$$(1, 2)$$$, $$$(3, 4)$$$, $$$(5, 6)$$$, $$$(7, 9)$$$, $$$(8, 10)$$$ 并从 $$$(1, 2)$$$, $$$(5, 6)$$$ 以及其他对中的最大元素。

如果 $$$x = 3$$$,则可以形成对 $$$(1, 3)$$$、$$$(4, 6)$$$、$$$(5, 7)$$$、$$$(2, 9)$$$、$$$(8, 10)$$$ 并从 $$$(1, 3)$$$、$$$(4, 6)$$$, $$$(5, 7)$$$。

在第三个测试用例中,$$$x = 0$$$ 是唯一的选项:您可以形成对 $$$(1, 3)$$$、$$$(2, 4)$$$ 并从它们中获取最大元素。