8670번 - Przegrody 다국어

Jaś wypisał na kartce wszystkie liczby od 1 do n w pewnej losowej kolejności, tworzącej pewien ciąg. Chciałby teraz wstawić jak najwięcej przegród do tej listy.

Przegrody może wstawiać tylko wtedy, gdy pomiędzy wstawianą przegrodą, ustawioną za k-tym elementem ciągu a początkiem ciągu, występuje każda z liczb od 1 do k. W szczególności ostatnią przegrodę Jaś może zawsze wstawić za n-tym elementem ciągu, bowiem będzie to permutacja liczb od 1 do n.

Pierwszy wiersz standardowego wejścia zawiera jedną liczbę całkowitą n (1 ≤ n ≤ 10⁶), oznaczającą liczbę elementów w ciągu.

Kolejny wiersz zawiera permutację n liczb całkowitych p₁, p₂, ..., p_n (1 ≤ p_i ≤ n), gdzie p_i oznacza i-tą liczbę w ciągu.

Pierwszy i jedyny wiersz wyjścia powinien zawierać jedną liczbę całkowitą, równą maksymalnej liczbie przegród, jakie może wstawić Jaś.

Jaś może ustawić przegrody w następujący sposób: 2 1 | 3 | 6 5 4 | 9 10 8 7 |.