Pairs
Contest: Educational Codeforces Round 100 (Rated for Div. 2)
Difficulty rating: 1900
Tags: binary search, constructive algorithms, greedy, two pointers

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?

Input format:
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$$$.

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

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
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.

Example input:
3
1
1
5
1 4 5 9 10
2
3 4

Example output:
1
3
1

Editorial:
Let's prove that in the set $$$b$$$ $$$x$$$ minimum elements will be from $$$x$$$ pairs where we'll take minimums and analogically $$$n - x$$$ maximums will be from $$$n - x$$$ pairs where we'll take maximums. By contradiction, let's look at two pairs $$$(a, b)$$$ ($$$a < b$$$) and $$$(c, d)$$$ ($$$c < d$$$), where we will take maximum from $$$(a, b)$$$ and minimum from $$$(c, d)$$$ and $$$b < c$$$, if we swap elements $$$b$$$ and $$$c$$$ and get pair $$$(a, c)$$$, $$$(b, d)$$$, the result won't change, but now minimum from pair $$$(b, d)$$$ will be less than maximum from $$$(a, c)$$$. So we can always make pairs in such a way that the chosen minimum from any pair will be less than the chosen maximum from any other pair.
Let's make set $$$nb$$$ as all elements which are not in $$$b$$$. In the same way, we can prove that $$$n - x$$$ minimums of $$$nb$$$ are from pairs where we took maximums and $$$x$$$ maximums are from pairs where we took minimums.
Let's say $$$b$$$ and $$$nb$$$ are sorted. Now we've proven that for a fixed $$$x$$$ we should pair $$$b_1, b_2, \dots, b_x$$$ with $$$nb_{n - x + 1}, nb_{n - x + 2}, \dots, nb_{n}$$$ and $$$b_{x + 1}, \dots, b_n$$$ with $$$nb_1, \dots, nb_{n - x}$$$. It's not hard to prove that it's optimal to pair $$$(b_1, nb_{n - x + 1})$$$, $$$(b_2, nb_{n - x + 2})$$$, ..., $$$(b_x, nb_n)$$$ and in the same way $$$(nb_1, b_{x + 1})$$$, $$$(nb_2, b_{x + 2})$$$, ..., $$$(nb_{n - x}, b_n)$$$.
For a fixed $$$x$$$ we can just check that constructed pairs are valid. But what happens if we move from $$$x$$$ to $$$x + 1$$$? If for $$$1 \le i \le n - x$$$ all $$$(nb_i, b_{x + i})$$$ was valid then for $$$x + 1$$$ all pairs $$$(nb_i, b_{x + 1 + i})$$$ will be valid as well. And on contrary, if at least one pair $$$(b_i, nb_{n - x + i})$$$ wasn't valid then for $$$x + 1$$$ the pair $$$(b_i, nb_{n - x - 1 + i})$$$ won't be valid as well.
Due to monotony we can find the maximum valid $$$x$$$ just checking only pairs $$$(b_i, nb_{n - x + i})$$$ and in the same way we can find maximum $$$n - x$$$ (minimum $$$x$$$) such that all pairs $$$(nb_i, b_{x + i})$$$ are valid. That's why all valid $$$x$$$-s form a segment, and we need to find its borders.
We can find a maximum $$$x$$$ (maximum $$$n - x$$$) with either binary search or with two pointers and print the length of the segment. Time complexity is either $$$O(n)$$$ or $$$O(n \log{n})$$$.