CF1463D.Pairs

You have $2n$ integers $1, 2, \dots, 2n$. You have to redistribute these $2n$ elements into $n$ pairs. After that, you choose $x$ pairs and take minimum elements from them, and from the other $n - x$ pairs, you take maximum elements.

Your goal is to obtain the set of numbers ${b_1, b_2, \dots, b_n}$ as the result of taking elements from the pairs.

What is the number of different $x$-s ($0 \le x \le n$) such that it's possible to obtain the set $b$ if for each $x$ you can choose how to distribute numbers into pairs and from which $x$ pairs choose minimum elements?

你有 $2n$ 个整数 $1, 2, \dots, 2n$。你需要将这 $2n$ 个元素重新分配为 $n$ 个数对。之后，你从中选择 $x$ 个数对，并从这 $x$ 个数对中各取最小值；而从其余 $n - x$ 个数对中，则各取最大值。

你的目标是：通过上述操作，恰好得到集合 $\{b_1, b_2, \dots, b_n\}$（即所取的 $n$ 个数构成该集合）。

问：满足条件的不同的 $x$ 的个数是多少（其中 $0 \le x \le n$）？这里，“满足条件”指：对于该 $x$，存在一种将 $2n$ 个数划分为 $n$ 个数对的方式，以及一种从中选出 $x$ 个数对以取其最小值（其余取最大值）的方式，使得最终取出的 $n$ 个数的集合恰好为 $b$。

The first line contains a single integer $t$ ($1 \le t \le 1000$) — the number of test cases.

The first line of each test case contains the integer $n$ ($1 \le n \le 2 \cdot 10^5$).

The second line of each test case contains $n$ integers $b_1, b_2, \dots, b_n$ ($1 \le b_1 \lt b_2 \lt \dots \lt b_n \le 2n$) — the set you'd like to get.

It's guaranteed that the sum of $n$ over test cases doesn't exceed $2 \cdot 10^5$.

第一行包含一个整数 $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 \lt b_2 \lt \dots \lt b_n \le 2n$）—— 你希望得到的集合。

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

For each test case, print one number — the number of different $x$-s such that it's possible to obtain the set $b$.

对于每个测试用例，输出一个数字——即能够得到集合 $b$ 的不同 $x$ 的个数。

In the first test case, $x = 1$ is the only option: you have one pair $(1, 2)$ and choose the minimum from this pair.

In the second test case, there are three possible $x$-s. If $x = 1$, then you can form the following pairs: $(1, 6)$, $(2, 4)$, $(3, 5)$, $(7, 9)$, $(8, 10)$. You can take minimum from $(1, 6)$ (equal to $1$) and the maximum elements from all other pairs to get set $b$.

If $x = 2$, you can form pairs $(1, 2)$, $(3, 4)$, $(5, 6)$, $(7, 9)$, $(8, 10)$ and take the minimum elements from $(1, 2)$, $(5, 6)$ and the maximum elements from the other pairs.

If $x = 3$, you can form pairs $(1, 3)$, $(4, 6)$, $(5, 7)$, $(2, 9)$, $(8, 10)$ and take the minimum elements from $(1, 3)$, $(4, 6)$, $(5, 7)$.

In the third test case, $x = 0$ is the only option: you can form pairs $(1, 3)$, $(2, 4)$ and take the maximum elements from both of them.

在第一个测试用例中，$x = 1$ 是唯一可行的选项：你只有一对 $(1, 2)$，并从中选取最小值。

在第二个测试用例中，存在三个可能的 $x$ 值。若 $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)$，并从这两对中均取最大值。