Monotoniczność 2
Limit pamięci: 256 MB
Niniejsze zadanie to trudniejsza wersja zadania
Monotoniczność z finału XVII OI.
Nie wystąpiła ona w samym konkursie.
Schematem monotoniczności ciągu liczb całkowitych
nazwiemy ciąg złożony ze znaków , lub =.
Znak reprezentuje relację pomiędzy liczbami i .
Na przykład, schematem monotoniczności ciągu jest .
Powiemy, że ciąg liczb , o schemacie monotoniczności
, realizuje pewien schemat monotoniczności
,
jeżeli dla każdego całkowitego zachodzi .
Innymi słowy, ciąg uzyskujemy, powtarzając odpowiednio
długo ciąg i ewentualnie odrzucając kilka ostatnich
wyrazów tego powtórzenia.
Na przykład, ciąg realizuje następujące schematy monotoniczności:
i wiele innych.
Dany jest ciąg liczb całkowitych .
Twoim zadaniem jest znalezienie najdłuższego jego podciągu
()
realizującego pewien zadany schemat monotoniczności .
Wejście
W pierwszym wierszu standardowego wejścia znajdują się dwie liczby całkowite
oraz (, ),
oddzielone pojedynczym odstępem i oznaczające odpowiednio długość ciągu
oraz długość schematu monotoniczności .
W drugim wierszu znajduje się liczb całkowitych pooddzielanych
pojedynczymi odstępami, oznaczających wyrazy badanego ciągu
().
W trzecim wierszu znajduje się znaków postaci <, > lub =,
pooddzielanych pojedynczymi odstępami, oznaczających kolejne wyrazy schematu monotoniczności.
Wyjście
W pierwszym wierszu standardowego wyjścia Twój program powinien wypisać
jedną liczbę całkowitą oznaczającą maksymalną długość podciągu ciągu
realizującego schemat monotoniczności .
W drugim wierszu Twój program powinien wypisać dowolny przykład takiego
podciągu , oddzielając jego wyrazy pojedynczymi
odstępami.
Przykład
Dla danych wejściowych:
7 3
2 4 3 1 3 5 3
< > =
poprawną odpowiedzią jest:
6
2 4 3 3 5 3
Autorzy zadania: Marian M. Kędzierski, Piotr Niedźwiedź.