D. Пары
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

У вас есть $$$2n$$$ целых чисел $$$1, 2, \dots, 2n$$$. Вы распределяете все $$$2n$$$ чисел на $$$n$$$ пар. После этого вы выбираете $$$x$$$ пар и из каждой из них берете минимум, а из каждой из оставшихся $$$n - x$$$ пар — максимум.

Ваша цель — получить в результате выбора элементов множество $$$\{b_1, b_2, \dots, b_n\}$$$.

Сколько существует различных $$$x$$$-в ($$$0 \le x \le n$$$) таких, что возможно получить множество $$$b$$$, если для каждого $$$x$$$ вы можете выбирать, как распределять числа и из каких $$$x$$$ пар выбирать минимумы?

Входные данные

В первой строке задано единственное целое число $$$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 < b_2 < \dots < b_n \le 2n$$$) — множество, которое вы хотите получить.

Гарантируется, что сумма $$$n$$$ по всем наборам не превосходит $$$2 \cdot 10^5$$$.

Выходные данные

Для каждого набора входных данных, выведите единственное число — количество различных $$$x$$$-в, таких, что возможно получить множество $$$b$$$.

Пример
Входные данные
3
1
1
5
1 4 5 9 10
2
3 4
Выходные данные
1
3
1
Примечание

В первом наборе входных данных, $$$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)$$$ и взять максимумы из обеих пар.