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