Problem Description

Research has shown that the order of Chinese characters does not necessarily affect reading. Scientists have conducted similar studies on sequences.

Given a sequence of positive integers, if the first term is the minimum value of all numbers in the sequence and the last term is the maximum value, we call this a correct sequence. For example, the sequences $[1, 3, 2, 4]$ and $[1, 2, 1, 2]$ are correct, but the sequence $[1, 3, 2]$ is not.

Given a sequence of length $n$ $[a_1, a_2, \ldots, a_n]$. For a segment of this sequence $[a_l, a_{l+1}, \ldots, a_r]$, if the first term of this segment is the minimum value within the segment and the last term is the maximum value within the segment, we call this a correct segment.

For the given sequence, find out the minimum number of segments it needs to be divided into, such that each segment is a correct segment. The sequence $[2, 3, 1, 1, 5, 1]$ can be divided into three correct segments: $[2, 3]$, $[1, 1, 5]$, and $[1]$.

You need to write a program that determines the minimum number of correct segments that can be formed from the given sequence.

Input Format

The first line contains an integer $n$.

The next line contains $n$ numbers, $a_1, a_2, \ldots, a_n$.

Output Format

Output the minimum number of correct segments that can be formed.

Sample Input and Output

Sample Input #1

5
5 4 3 2 1

Sample Output #1

5

Sample Input #2

4
1 3 2 4

Sample Output #2

1

Sample Input #3

6
2 3 1 1 5 1

Sample Output #3

3

Notes

For $30\%$ of the data, $1 \leq n \leq 500$.

For $60\%$ of the data, $1 \leq n \leq 5000$.

For all data, $1 \leq n \leq 3 \times 10^5$, $1 \leq a_i \leq 10^9$.

见题面 Input 部分

见题面 Output 部分