시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 4 3 2 66.667%

문제

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 ≤ 106), oznaczającą liczbę elementów w ciągu.

Kolejny wiersz zawiera permutację n liczb całkowitych p1, p2, ..., pn (1 ≤ pin), gdzie pi 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ś.

예제 입력 1

10
2 1 3 6 5 4 9 10 8 7

예제 출력 1

4

힌트

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