B. Колода карт
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

У вас есть колода из $$$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}$$$.

Для заданной колоды, определите колоду с максимально возможной упорядоченностью, которую вы можете получить, используя алгоритм, описанный выше.

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

В первой строке задано одно целое число $$$t$$$ ($$$1 \le t \le 1000$$$) — количество наборов входных данных.

В первой строке каждого набора задано одно целое число $$$n$$$ ($$$1 \le n \le 10^5$$$) — количество карт в колоде.

Во второй строке заданы $$$n$$$ целых чисел $$$p_1, p_2,\dots, p_n$$$ ($$$1 \le p_i \le n$$$; $$$p_i \neq p_j$$$ если $$$i \neq j$$$) — значения карт в колоде в порядке снизу вверх.

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

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

Для каждого набора входных данных, выведите колоду с максимально возможной упорядоченностью. Выводите значения карт начиная с нижних в колоде.

Если существует несколько ответов, выведите любой из них.

Пример
Входные данные
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
Примечание

В первом наборе входных данных одна из оптимальных стратегий — следующая:

  1. возьмем $$$1$$$ карту сверху $$$p$$$ и перенесем ее в $$$p'$$$: $$$p$$$ станет $$$[1, 2, 3]$$$, $$$p'$$$ станет $$$[4]$$$;
  2. возьмем $$$1$$$ карту сверху $$$p$$$: $$$p$$$ станет $$$[1, 2]$$$, $$$p'$$$ станет $$$[4, 3]$$$;
  3. возьмем $$$1$$$ карту сверху $$$p$$$: $$$p$$$ станет $$$[1]$$$, $$$p'$$$ станет $$$[4, 3, 2]$$$;
  4. возьмем $$$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$$$.

Во втором наборе одна из оптимальных стратегий такая:

  1. возьмем $$$4$$$ карты сверху $$$p$$$ и переместим их в $$$p'$$$: $$$p$$$ станет $$$[1]$$$, $$$p'$$$ станет $$$[5, 2, 4, 3]$$$;
  2. возьмем $$$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$$$.

Во третьем наборе одна из оптимальных стратегий такая:

  1. возьмем $$$2$$$ карты сверху $$$p$$$ и переместим их в $$$p'$$$: $$$p$$$ станет $$$[4, 2, 5, 3]$$$, $$$p'$$$ станет $$$[6, 1]$$$;
  2. возьмем $$$2$$$ карты сверху $$$p$$$ и переместим их в $$$p'$$$: $$$p$$$ станет $$$[4, 2]$$$, $$$p'$$$ станет $$$[6, 1, 5, 3]$$$;
  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$$$.