8860번 - Hossa 다국어

Na giełdy światowe na dobre powróciły wzrosty i od dawna mówi się o kolejnej hossie. Czym dokładnie jest jednak hossa? Na to pytanie postanowił odpowiedzieć znany matematyk i ekonomista - pan Wacław. Pan Wacław przez wiele miesięcy starał się określić ścisłe granice hoss i bess na wykresie Warszawskiego Indeksu Giełdowego (WIG). Wreszcie, po wielu nieudanych próbach, Pan Wacław podał formalną definicję, która jego zdaniem w pełni opisuje moment wystąpienia hossy na giełdzie. Oto ona:

Niech a₁, a₂, ...., a_n  - wartość WIG w kolejnych dniach notowań. Możemy założyć, że jest to n-elementowy ciąg różnych liczb naturalnych. Mówimy, że ciąg a jest hossą wtedy, gdy dla każdych trzech pozycji w ciągu i, j, k (i<j<k) jeżeli a_i<a_j to a_k>a_i. Intuicyjnie, jeżeli między dwoma dniami i oraz j kurs wzrósł z a_i do a_j to mamy pewność, że kurs nigdy nie spadnie w kolejnych dniach do lub poniżej wartości a_i.

Przykładowo, wszystkie hossy składające się z 4 elementów 1,2,3,4 to:

(1,2,3,4), (2,1,3,4), (1,3,2,4), (3,1,2,4), (3,2,1,4), (1,2,4,3), (2,1,4,3), (1,4,2,3), (1,4,3,2), (4,1,2,3), (4,2,1,3), (4,1,3,2), (4,3,1,2), (4,3,2,1)

Hossą nie jest na przykład ciąg (3,2,4,1), bo kurs wzrósł z 3 do 4, a później spadł do 1.

Każdą hossę możemy zapisać jako LmR - gdzie: m - najwyższa wartość w ciągu, L - elementy ciągu po lewej stronie m, P - elementy ciągu po prawej stronie m. Przykładowo, dla hossy (1,2,4,3): m = 4, L = (1,2), P = (3). Łatwo zauważyć, że elementy L (lub P) tworzą hossę składającą się z mniejszej liczby elementów.

Definicja hossy Pana Wacława odniosła ogromny sukces - został on nawet zaproszony na Wall Street, aby publicznie wygłosić referat. Jednym z jego elementów jest przedstawienie kilku przykładów ciągów, które są hossami. Aby o żadnej nie zapomnieć, Pan Wacław postanowił wprowadzić porządek, który pozwoliłby na porównanie ze sobą dwóch hoss. Oto jego definicja:

Mówimy, że dla dwóch różnych hoss H₁ = L₁mP₁ i H₂ = L₂mP₂ zachodzi H₁<H₂ (hossa H₁ jest mniejsza od hossy H₂) wtedy gdy, H₁ i H₂ składają się z tych samych liczb (H₂ jest permutacją elementów ciągów H₁) oraz:

1. liczba elementów w P₁ jest mniejsza od liczby elementów w P₂
2. jeżeli liczba elementów P₁ i P₂ jest taka sama to sprawdzamy czy P₁ < P₂ (czyli czy hossa P₁ jest mniejsza od hossy P₂)
3. jeżeli P₁ jest tym samym ciągiem co P₂, to sprawdzamy czy L₁ < L₂

Przykładowo, możemy posortować wszystkie hossy składające się z 4 elementów i otrzymać ciąg hoss przedstawiony w pierwszej definicji. Niektóre z możliwych porównań:

• (1,2,3,4) < (2,1,3,4) - zachodzi przypadek c, tj. (1,2,3) < (2,1,3). Możemy stwierdzić, że (1,2,3) < (2,1,3), ponieważ znowu zachodzi przypadek c, tj. (1,2)<(2,1). Możemy stwierdzić, że (1,2)<(2,1), ponieważ zachodzi przypadek a.
• (1,4,2,3) < (1,4,3,2) - zachodzi przypadek b, tj. (2,3) < (3,2).

Tuż przed wyjazdem, Pan Wacław zalał kawą jeden z przykładów przygotowanych do pokazania maklerom na Wall Street. Szczęśliwie wie on, że zalana hossa jest bezpośrednim następnikiem pewnej innej hossy H. Pan Wacław poprosił Ciebie, żebyś napisał program, który pomoże mu odtworzyć ten przykład. Innymi słowy, Twoim zadaniem jest mając dany opis hossy H, wypisać elementy hossy X, takiej że:

• H < X
• dla każdej innej od X hossy H', takiej że H<H', zachodzi X<H'

Możesz założyć, że dla danych testowych taka hossa zawsze istnieje.

Przykładowo, bezpośrednim następnikiem hossy (1,2,3,4) jest (2,1,3,4), (2,1,3,4) jest (1,3,2,4), (1,3,2,4) jest (3,1,2,4), itd.

W pierwszej linii wejścia znajduje się jedna liczba całkowita n (2<=n<=1000000). W następnej linii znajduje się n różnych liczb naturalnych, nie większych od 1000000, oddzielonych pojedynczym odstępem. Są to kolejne elementy pewnej hossy H.

Twój program powinien wypisać ciąg n liczb naturalnych oddzielonych pojedynczym odstępem. Są to kolejne elementy hossy będącej bezpośrednim następnikiem hossy H.