Superliczby w permutacji

Limit pamięci: 32 MB

Permutacja -elementowa jest ciągiem -elementowym składającym się z różnych liczb ze zbioru . Przykładowo, ciąg jest permutacją -elementową.

W permutacjach liczb będą interesować nas najdłuższe rosnące podciągi. W przykładowej permutacji mają one długość i istnieją dokładnie dwa takie podciągi, a mianowicie oraz .

Superliczbą nazwiemy każdą liczbę, która należy do dowolnego z najdłuższych rosnących podciągów. W permutacji superliczbami są , zaś liczba superliczbą nie jest.

Twoim zadaniem jest dla zadanej permutacji znaleźć wszystkie superliczby.

Zadanie

Napisz program, który:

• wczyta permutację ze standardowego wejścia,
• znajdzie wszystkie superliczby,
• wypisze znalezione superliczby na standardowe wyjście.

Wejście

Wejście składa się z dwóch wierszy. W pierwszym wierszu znajduję się jedna liczba , . W drugim wierszu znajduję się liczb tworzących permutację -elementową, pooddzielanych pojedynczymi odstępami.

Wyjście

Wyjście powinno się składać z dwóch wierszy. W pierwszym wierszu powinna znaleźć się jedna liczba - liczba superliczb w wejściowej permutacji. W drugim powinny znaleźć się superliczby pooddzielane pojedynczymi odstępami, wymienione w kolejności rosnącej.

Przykład

Dla danych wejściowych:

5
2 1 4 5 3

poprawną odpowiedzią jest:

4
1 2 4 5

Autor zadania: Jakub Pawlewicz.