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:

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ź.