Дано число \(n\) и массив \(a_1, a_2, \ldots, a_n\). Необходимо переставить числа в массиве \(a\) так, чтобы сумма \(\textbf{MEX}\) на всех префиксах массива (\(i\)-й префикс — это \(a_1, a_2, \ldots, a_i\)) была максимальна.
Формально, вам нужно найти массив \(b_1, b_2, \ldots, b_n\), такой что наборы чисел массивов \(a\) и \(b\) совпадают (то есть массив \(b\) получается некоторой перестановкой чисел в массиве \(a\)) и \(\sum\limits_{i=1}^{n} \textbf{MEX}(b_1, b_2, \ldots, b_i)\) максимальна.
Напомним, что \(\textbf{MEX}\) множества целых неотрицательных чисел — такое минимальное целое неотрицательное число, которое не входит в это множество.
Например, \(\textbf{MEX}(\{1, 2, 3\}) = 0\), \(\textbf{MEX}(\{0, 1, 2, 4, 5\}) = 3\).
Выходные данные
Для каждого набора входных данных выведите массив \(b_1, b_2, \ldots, b_n\), являющийся оптимальной перестановкой чисел \(a_1, a_2, \ldots, a_n\), то есть сумма \(\textbf{MEX}\) на всех его префиксах максимальна.
Если существует несколько оптимальных ответов, вы можете найти любой.
Примечание
В первом наборе входных данных в ответе \(\textbf{MEX}\) на префиксах будет таким:
- \(\textbf{MEX}(\{0\}) = 1\)
- \(\textbf{MEX}(\{0, 1\}) = 2\)
- \(\textbf{MEX}(\{0, 1, 2\}) = 3\)
- \(\textbf{MEX}(\{0, 1, 2, 3\}) = 4\)
- \(\textbf{MEX}(\{0, 1, 2, 3, 4\}) = 5\)
- \(\textbf{MEX}(\{0, 1, 2, 3, 4, 7\}) = 5\)
- \(\textbf{MEX}(\{0, 1, 2, 3, 4, 7, 3\}) = 5\)
Сумма
\(\textbf{MEX} = 1 + 2 + 3 + 4 + 5 + 5 + 5 = 25\). Можно показать, что это максимальная возможная сумма
\(\textbf{MEX}\) на префиксах.