配对(Pairs)

题目描述

你有 $2n$ 个整数 $1,2,\dots,2n$。要把这 $2n$ 个数重新分成 $n$ 对。之后，你选出 $x$ 对并从中取较小值，其余 $n-x$ 对中取较大值。 你的目标是：通过对"每对如何配对"以及"从哪 $x$ 对取较小值"的选择，最终得到集合 $\{b_1,\dots,b_n\}$。 问：有多少个不同的 $x\ (0\le x\le n)$ 使得可以做到？（对每个 $x$ 都可重新安排配对方式。）

输入格式

第一行一个整数 $t\ (1\le t\le 1000)$ — 测试组数。 每组：第一行 $n\ (1\le n\le 2\cdot 10^5)$；第二行 $n$ 个整数 $b_1\dots b_n\ (1\le b_1<b_2<\cdots<b_n\le 2n)$。 保证所有组 $n$ 之和 $\le 2\cdot 10^5$。

输出格式

每组一行整数 — 可行的 $x$ 的个数。

样例输入 #1

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

样例输出 #1

1
3
1

数据范围

$1\le t\le 1000$；$1\le n\le 2\cdot 10^5$；$1\le b_1<\cdots<b_n\le 2n$；$\sum n\le 2\cdot 10^5$。

知识点与难度

本题涉及的知识点从属于 GESP 五级，难度等级：⭐⭐⭐

测试点分布