Pairs

题意翻译

## 题目描述 你有 $2n$ 个整数 $1,2,\cdots,2n$，你需要将其分成 $n$ 对，然后选择其中 $x$ 对，取出其中的较小数，并取出其余 $n-x$ 对中的较大数，使得最终取出的数组成的集合为 $\{b_1,b_2,\cdots,b_n\}$。问有多少个满足题意的 $x$。 数据范围：$1 \le t \le 1000$，$\sum n \le 2 \cdot 10^5$。 ## 输入格式 输入形如： $t$ $case_1$ $case_2$ $\vdots$ $case_t$ 其中 $case_i$ 表示第 $i$ 组数据，具体形如： $n$ $b_1,b_2,\cdots,b_n$ ## 输出格式 输出形如： $ans_1$ $ans_2$ $\vdots$ $ans_t$ 其中 $ans_i$ 表示第 $i$ 组数据的答案。 ## 样例解释 在第一组数据中，只有 $x=1$ 符合题意：取 $(1,2)$ 的较小数。 在第二组数据中，$x=1,2,3$ 符合题意，具体方案如下： 若 $x=1$，将所有数分成 $(1,6)$，$(2,4)$，$(3,5)$，$(7,9)$，$(8,10)$，取 $(1,6)$ 的较小数和其余对的较大数。 若 $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)$，取这两对的较大数。

题目描述

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?

输入输出格式

输入格式

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 < b_2 < \dots < 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 $ .

输出格式

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

输入输出样例

输入样例 #1

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

输出样例 #1

1
3
1

说明

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.