Mistrzostwa Polski Szkół Średnich w Programowaniu Zespołowym 2023

Old page Regulations Schedule RODO info Ranking

Problem description


Najmniejszy leksykograficznie LIS
(najmniejszy-lis)
Memory limit: 64 MB
Time limit: 1.00 s

Napisz program, który dla danego ciągu liczb a1, a2, …, aN wyznaczy jego podciąg rosnący o największej długości. Ponieważ tak sprecyzowany problem ma niejednoznaczną odpowiedź, więc program Twój powinien wypisać taki podciąg, który jest dodatkowo najmniejszy leksykograficznie.

Wejście

W pierwszym wierszu podana jest długość ciągu N. W drugim wierszu zapisanych jest N liczb naturalnych a1, a2, …, aN, oddzielonych pojedynczym odstępem.

Wyjście

W pierwszym wierszu wyjścia powinna się znaleźć długość najdłuższego podciągu rosnącego. Natomiast w drugim wierszu najmniejszy leksykograficznie podciąg o takiej długości.

Ograniczenia

1 ≤ N ≤ 106, 1 ≤ ai ≤ 106.

Przykład

Input Output Explanation
13
16 5 8 6 1 10 5 2 15 3 2 4 1
4
1 2 3 4 

Istnieją trzy rosnące podciągi o długości 4, mianowicie: (5,8,10,15), (5,6,10,15) oraz (1,2,3,4). Ten trzeci jest oczywiście najmniejszy leksykograficznie.