복호화

어떤 단어의 첫 글자와 마지막 글자를 그대로 두고 나머지 글자를 임의로 재배열해도 그 글은 여전히 비교적 쉽게 읽힌다고 알려져 있다. 정보학 연구실에서는 수열에 대한 비슷한 현상을 연구한다.

양의 정수로 이루어진 수열이 올바른 수열이라는 것은 이 수열의 첫 번째 수가 최솟값이고 마지막 수가 최댓값인 경우를 말한다. 예를 들어 수열 $[1, 3, 2, 4]$와 $[1, 2, 1, 2]$는 올바른 수열이고, 수열 $[1, 3, 2]$는 아니다.

수열 $[a_1, a_2, \ldots, a_n]$이 주어진다. 주어진 수열의 연속한 원소들로 이루어진 구간 $[a_l, a_{l+1}, \ldots, a_r]$이 올바른 구간이라는 것은 이 구간이 올바른 수열인 경우, 즉 $a_l$이 이 구간의 최솟값이고 $a_r$이 최댓값인 경우를 말한다.

연구의 일환으로 주어진 수열을 서로 겹치지 않는 올바른 구간들로 최소 개수로 나누려고 한다. 예를 들어 수열 $[2, 3, 1, 1, 5, 1]$은 세 개의 올바른 구간 $[2, 3]$, $[1, 1, 5]$, $[1]$로 나눌 수 있다.

주어진 수열을 최소 몇 개의 올바른 구간으로 나눌 수 있는지 구하는 프로그램을 작성하시오.

첫째 줄에는 주어진 수열의 원소 개수 $n$이 주어진다 ($1 \le n \le 300\,000$).

둘째 줄에는 주어진 수열 $a_1, a_2, \ldots, a_n$이 주어진다 ($1 \le a_i \le 10^9$).

주어진 수열을 나눌 수 있는 올바른 구간 개수의 최솟값을 출력한다.