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.