28. НВП с восстановлением ответа

Дана последовательность, требуется найти её наибольшую возрастающую подпоследовательность.

Напомним:

Последовательность x называется подпоследовательностью последовательности y, если x получается из y удалением нескольких (возможно, нуля или всех) элементов.

Наибольшая возрастающая подпоследовательность - строго возрастающая подпоследовательность наибольшей длины.

В первой строке входных данных задано число N — длина последовательности (1 $\le$ N $\le$ 1000). Во второй строке задается сама последовательность (разделитель — пробел). Элементы последовательности — целые числа, не превосходящие 10000 по модулю.

Требуется вывести наибольшую возрастающую подпоследовательность данной последовательности. Если таких подпоследовательностей несколько, необходимо вывести одну (любую) из них.