У вас есть колода из \(n\) карт, и вы хотите переупорядочить ее по-новому.
У каждой карты есть целое значение от \(1\) по \(n\) равное \(p_i\). Все \(p_i\) попарно различны. Карты в колоде пронумерованы снизу вверх, таким образом \(p_1\) лежит внизу колоды, а \(p_n\) — на самом верху.
Вы перекладываете колоду шаг за шагом. На каждом шаге вы выбираете некоторое целое \(k > 0\), берете \(k\) верхних карт из вашей колоды и кладете их, не меняя порядка, на верх новой колоды. Вы применяете данную операцию, пока ваша первоначальная колода не опустеет. (Для лучшего понимания изучите примечания к тестовым примерам.)
Назовем упорядоченностью колоды сумму \(\sum\limits_{i = 1}^{n}{n^{n - i} \cdot p_i}\).
Для заданной колоды, определите колоду с максимально возможной упорядоченностью, которую вы можете получить, используя алгоритм, описанный выше.
Выходные данные
Для каждого набора входных данных, выведите колоду с максимально возможной упорядоченностью. Выводите значения карт начиная с нижних в колоде.
Если существует несколько ответов, выведите любой из них.
Примечание
В первом наборе входных данных одна из оптимальных стратегий — следующая:
- возьмем \(1\) карту сверху \(p\) и перенесем ее в \(p'\): \(p\) станет \([1, 2, 3]\), \(p'\) станет \([4]\);
- возьмем \(1\) карту сверху \(p\): \(p\) станет \([1, 2]\), \(p'\) станет \([4, 3]\);
- возьмем \(1\) карту сверху \(p\): \(p\) станет \([1]\), \(p'\) станет \([4, 3, 2]\);
- возьмем \(1\) карту сверху \(p\): \(p\) опустеет, а \(p'\) станет \([4, 3, 2, 1]\).
В результате упорядоченность
\(p'\) равна
\(4^3 \cdot 4 + 4^2 \cdot 3 + 4^1 \cdot 2 + 4^0 \cdot 1\) \(=\) \(256 + 48 + 8 + 1 = 313\).
Во втором наборе одна из оптимальных стратегий такая:
- возьмем \(4\) карты сверху \(p\) и переместим их в \(p'\): \(p\) станет \([1]\), \(p'\) станет \([5, 2, 4, 3]\);
- возьмем \(1\) карту сверху \(p\) и перенесем ее в \(p'\): \(p\) опустеет, а \(p'\) станет \([5, 2, 4, 3, 1]\);
В результате упорядоченность
\(p'\) равна
\(5^4 \cdot 5 + 5^3 \cdot 2 + 5^2 \cdot 4 + 5^1 \cdot 3 + 5^0 \cdot 1\) \(=\) \(3125 + 250 + 100 + 15 + 1 = 3491\).
Во третьем наборе одна из оптимальных стратегий такая:
- возьмем \(2\) карты сверху \(p\) и переместим их в \(p'\): \(p\) станет \([4, 2, 5, 3]\), \(p'\) станет \([6, 1]\);
- возьмем \(2\) карты сверху \(p\) и переместим их в \(p'\): \(p\) станет \([4, 2]\), \(p'\) станет \([6, 1, 5, 3]\);
- возьмем \(2\) карты сверху \(p\) и переместим их в \(p'\): \(p\) опустеет, а \(p'\) станет \([6, 1, 5, 3, 4, 2]\).
В результате упорядоченность
\(p'\) равна
\(6^5 \cdot 6 + 6^4 \cdot 1 + 6^3 \cdot 5 + 6^2 \cdot 3 + 6^1 \cdot 4 + 6^0 \cdot 2\) \(=\) \(46656 + 1296 + 1080 + 108 + 24 + 2 = 49166\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
4
1 2 3 4
5
1 5 2 4 3
6
4 2 5 3 6 1
1
1
|
4 3 2 1
5 2 4 3 1
6 1 5 3 4 2
1
|