Pairs (Codeforces 1463D)
Tags: 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: 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: For each test case, print one number — the number of different $$$x$$$-s such that it's possible to obtain the set $$$b$$$.

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.

Sample Inputs:
3
1
1
5
1 4 5 9 10
2
3 4

Sample Outputs:
1
3
1

Solution (Python):
import sys
input = sys.stdin.readline

def solve():
    n = int(input())
    arr = list(map(int, input().split()))
    S = set(arr)
    exc = cnt1 = 0
    for i in range(1, 2 * n + 1):
        if i not in S:
            exc += 1
            continue
        if exc:
            cnt1 += 1
            exc -= 1
    f = n - cnt1
    exc = cnt2 = 0
    for i in range(2 * n, 0, -1):
        if i not in S:
            exc += 1
            continue
        if exc:
            cnt2 += 1
            exc -= 1
    b = cnt2
    return b - f + 1
for _ in range(int(input())):
    print(solve())

Solution (Python):
n = int(input())
for _ in range(n):
    m = int(input())
    lst = list(map(int, input().split()))
    used = 0
    smallest = m
    for num in lst:
        if num - 1 > used:
            smallest -= 1
            used += 2
        else:
            used += 1
    used = 0
    greatest = 0
    for num in lst[::-1]:
        if 2 * m - num > used:
            greatest += 1
            used += 2
        else:
            used += 1
    print(greatest - smallest + 1)

Solution (Python):
t = int(input())
for _ in range(t):
    n = int(input())
    b = list(map(int, input().split()))
    max_force = 0
    min_force = 0
    legacy = 0
    possibility = 0
    for i in b:
        jump = i - legacy - 1
        possibility += jump
        if possibility > 0:
            possibility -= 1
        else:
            min_force += 1
        legacy = i
    possibility = 0
    legacy = 2 * n + 1
    for i in reversed(b):
        jump = legacy - i - 1
        possibility += jump
        if possibility > 0:
            possibility -= 1
        else:
            max_force += 1
        legacy = i
    print(n - max_force - min_force + 1)