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.