블록 나누기

쉬는 시간, 하윤이는 길이 $N$의 순열 $P=[P_1,P_2,\cdots,P_N]$을 여러 개의 레고 블록으로 나누려고 한다.

길이 $N$의 순열이란 $1$ 이상 $N$ 이하의 정수가 각각 정확히 한 번씩 등장하는 수열이다. 각 블록은 순열에서 연속한 하나 이상의 원소로 이루어지며, 블록의 순서는 원래 순열에서의 순서를 따른다.

하윤이는 다음 조건을 모두 만족하도록 순열을 나누려고 한다.

• 각 원소는 정확히 하나의 블록에 포함되어야 한다.
• 같은 블록에 포함된 원소들은 원래 순열에서 연속한 위치에 있어야 한다.
• 각 블록의 원소를 블록 안에서 오름차순으로 정렬한 뒤, 블록들을 앞에서부터 이어 붙이면 $[1,2,\cdots,N]$이 되어야 한다.

예를 들어 $P=[3,4,2,1,5,7,6]$이라면 $(3,4,2,1)$, $(5)$, $(7,6)$의 세 블록으로 나눌 수 있다.

조건을 만족하면서 만들 수 있는 블록 개수의 최댓값을 구하여라.

입력은 다음과 같은 형식으로 주어진다.

$N$ $P_1\ P_2\ \cdots\ P_N$

첫째 줄에 조건을 만족하면서 순열을 나누어 얻을 수 있는 블록 개수의 최댓값을 출력한다.

• $1 \leq N \leq 1\ 000\ 000$.
• $1 \leq P_i \leq N$ ($1 \leq i \leq N$).
• $P_i \neq P_j$ ($1 \leq i < j \leq N$).