У Ивана есть массив, состоящий из n различных целых чисел. Он решил упорядочить элементы массива по возрастанию. Так как Иван является фанатом сортировки слиянием, он решил представить массив в виде одной или нескольких возрастающих последовательностей, которые затем он планирует слить в один отсортированный массив.
Представление массива в виде возрастающих последовательностей Иван формирует с помощью следующего алгоритма.
До тех пор, пока в массиве есть хотя бы одно невыписанное число, он повторяет следующую процедуру:
- просматривает массив слева направо;
- во время очередного просмотра обращает внимание только на не выписанные ранее числа;
- если рассматриваемое им в данный момент число — первое невыписанное число во время текущего просмотра, или же оно больше предыдущего выписанного во время текущего просмотра числа, то он выписывает рассматриваемое число.
Например, если массив Ивана имеет вид [1, 3, 2, 5, 4], то всего он выполнит два просмотра. На первом из них он выпишет числа [1, 3, 5], а на втором — [2, 4].
Напишите программу, которая автоматизирует подготовительную работу Ивана — найдёт представление заданного массива в виде одной или нескольких возрастающих последовательностей в соответствии с описанным выше алгоритмом.