Minimum Correct Segments Partition

Given a sequence of positive integers \(a_1,a_2,\ldots,a_n\), a segment (i.e. contiguous subarray) \([a_l,a_{l+1},\ldots,a_r]\) is defined as correct if the first element of the segment is equal to the minimum element in that segment and the last element is equal to the maximum element in that segment. For example, the segments \([1, 3, 2, 4]\) and \([1, 2, 1, 2]\) are correct, while \([1, 3, 2]\) is not.

Your task is: given a sequence \([a_1, a_2, \ldots, a_n]\), determine the minimum number of segments into which the sequence can be partitioned such that every segment is correct. For instance, the sequence [2, 3, 1, 1, 5, 1] can be partitioned into three correct segments: [2, 3], [1, 1, 5], and [1].

Note: A segment \([a_l, \ldots, a_r]\) is correct if and only if \(a_l = \min\{a_l, a_{l+1}, \ldots, a_r\}\) and \(a_r = \max\{a_l, a_{l+1}, \ldots, a_r\}\).

inputFormat

The first line contains a single integer \(n\) (the length of the sequence). The second line contains \(n\) positive integers separated by spaces.

outputFormat

Output a single integer: the minimum number of segments needed, where each segment is correct as per the definition.

sample

4
1 3 2 4

1