Przegrody

Limit pamięci: 32 MB

Jaś wypisał na kartce wszystkie liczby od do 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 -tym elementem ciągu a początkiem ciągu, występuje każda z liczb od do . W szczególności ostatnią przegrodę Jaś może zawsze wstawić za -tym elementem ciągu, bowiem będzie to permutacja liczb od do .

Wejście

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

Kolejny wiersz zawiera permutację liczb całkowitych (), gdzie oznacza -tą liczbę w ciągu. W testach wartych około punktów zachodzi , w testach wartych około punktów zachodzi .

Wyjście

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

Przykład

Dla danych wejściowych:

10
2 1 3 6 5 4 9 10 8 7

poprawną odpowiedzią jest:

4

Wyjaśnienie do przykładu: Jaś może ustawić przegrody w następujący sposób: .

Autor zadania: Jacek Tomasiewicz.