题目描述

给一个序列，若序列首项为数列中所有数的最小值，末项为数列中的最大值，则我们称这是个正确的数列。

• 例如，序列 $[1, 3, 2, 4]$ 和 $[1, 2, 1, 2]$ 是正确的，但序列 $[1, 3, 2]$ 不是。

现在给你一个长度为 $n$ 的数组 $a$。对于该数组的某个段 $[a_l, a_{l+1}, \ldots, a_r]$。

• 若满足 $a_l=\min(a_l,a_{l+1},\ldots,a_r),\ a_r=\max(a_l,a_{l+1},\ldots,a_r)$。则区间 $[l,r]$ 为正确的段。

对于给定的序列，请求出该序列至少需要被分成多少段，才能使得每段均为正确的。序列 $[2, 3, 1, 1, 5, 1]$ 可以分为三个正确的段：$[2, 3]$ 和 $[1, 1, 5]$ 和 $[1]$。

编写程序，确定可以划分的最小正确段数。

输入格式

第一行一个整数 $n$。

接下来一行 $n$ 个数，分别为 $a_1,a_2,\ldots,a_n$。

输出格式

输出可以划分的最小正确段数。

5
5 4 3 2 1

5

4
1 3 2 4

1

6
2 3 1 1 5 1

3

4
2 3 3 1

2

提示

• 对于 $30\%$ 的数据，$1 \leq n \leq 500$。

• 对于 $60\%$ 的数据，$1 \leq n \leq 5000$。

• 对于所有数据，$1 \leq n \leq3 \times 10^5$，$1\leq a_i \leq 10^9$。