칸막이

$1$부터 $n$까지의 모든 정수가 어떤 순서로 한 줄에 나열되어 하나의 수열을 이룹니다. 이 수열은 $1$부터 $n$까지의 순열입니다.

이 수열에 칸막이를 최대한 많이 세우려고 합니다. 칸막이는 수열의 인접한 두 원소 사이(또는 맨 끝)에 세울 수 있습니다.

$k$번째 원소 바로 뒤에 칸막이를 세울 수 있는 조건은, 수열의 처음부터 $k$번째 원소까지에 $1$부터 $k$까지의 모든 수가 정확히 한 번씩 등장하는 것입니다. 즉, 앞쪽 $k$개의 원소가 집합 $\{1, 2, \ldots, k\}$와 같아야 합니다. 특히 $n$번째 원소 바로 뒤에는 항상 칸막이를 세울 수 있는데, 전체 수열이 $1$부터 $n$까지의 순열이기 때문입니다.

세울 수 있는 칸막이의 최대 개수를 구하세요.

첫째 줄에 수열의 길이를 나타내는 정수 $n$ ($1 \le n \le 10^6$)이 주어집니다.

둘째 줄에 $1$부터 $n$까지의 순열 $p_1, p_2, \ldots, p_n$ ($1 \le p_i \le n$)이 공백으로 구분되어 주어집니다. 여기서 $p_i$는 수열의 $i$번째 수입니다.

세울 수 있는 칸막이의 최대 개수를 한 줄에 출력합니다.

예를 들어 수열이 2 1 3 6 5 4 9 10 8 7일 때, 칸막이는 다음과 같이 세울 수 있습니다: 2 1 | 3 | 6 5 4 | 9 10 8 7 |. 이 경우 칸막이는 모두 $4$개입니다.