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