B. Подготовка к сортировке слиянием
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

У Ивана есть массив, состоящий из n различных целых чисел. Он решил упорядочить элементы массива по возрастанию. Так как Иван является фанатом сортировки слиянием, он решил представить массив в виде одной или нескольких возрастающих последовательностей, которые затем он планирует слить в один отсортированный массив.

Представление массива в виде возрастающих последовательностей Иван формирует с помощью следующего алгоритма.

До тех пор, пока в массиве есть хотя бы одно невыписанное число, он повторяет следующую процедуру:

  • просматривает массив слева направо;
  • во время очередного просмотра обращает внимание только на не выписанные ранее числа;
  • если рассматриваемое им в данный момент число — первое невыписанное число во время текущего просмотра, или же оно больше предыдущего выписанного во время текущего просмотра числа, то он выписывает рассматриваемое число.

Например, если массив Ивана имеет вид [1, 3, 2, 5, 4], то всего он выполнит два просмотра. На первом из них он выпишет числа [1, 3, 5], а на втором — [2, 4].

Напишите программу, которая автоматизирует подготовительную работу Ивана — найдёт представление заданного массива в виде одной или нескольких возрастающих последовательностей в соответствии с описанным выше алгоритмом.

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

В первой строке содержится целое положительное число n (1 ≤ n ≤ 2·105) — количество чисел в массиве Ивана.

Во второй строке содержится последовательность различных целых чисел a1, a2, ..., an (1 ≤ ai ≤ 109) — массив Ивана.

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

Выведите представление заданного массива в виде одной или нескольких возрастающих последовательностей в соответствии с описанным выше алгоритмом. Каждую последовательность выводите на новой строке.

Примеры
Входные данные
5
1 3 2 5 4
Выходные данные
1 3 5 
2 4
Входные данные
4
4 3 2 1
Выходные данные
4 
3
2
1
Входные данные
4
10 30 50 101
Выходные данные
10 30 50 101