P9290 [ROI 2018] Decryption

译自 [ROI 2018 Day2](https://neerc.ifmo.ru/school/archive/2017-2018.html) T1. [Расшифровка](https://neerc.ifmo.ru/school/archive/2017-2018/ru-olymp-roi-2018-day2.pdf) ([Decryption](https://codeforces.com/gym/102154/problem/B))。

研究表明，汉字的顺序并不一定能影响阅读。科学家们对数列进行了类似的研究。 给一个正整数数列，若数列首项为数列中所有数的最小值，末项为数列中的最大值，则我们称这是个正确的数列。例如，序列 $[1, 3, 2, 4]$ 和 $[1, 2, 1, 2]$ 是正确的，但序列 $[1, 3, 2]$ 不是。 给出长度为 $n$ 的序列 $[a_1, a_2, \ldots, a_n]$。对于该序列的某个片段 $[a_l, a_{l+1}, \ldots, a_r]$, 若该片段的首项为该片段中的最小值，末项为该片段中的最大值，则我们称这是个正确的片段。 对于给定的序列，请求出该序列至少需要被分成多少段，才能使得每个片段均为正确的片段。序列 $[2, 3, 1, 1, 5, 1]$ 可以分为三个正确的段：$[2, 3]$ 和 $[1, 1, 5]$ 和 $[1]$。 需要编写一个程序，该程序按给定的顺序确定可以划分的最小正确段数。

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

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

- 子任务 1（30 分），$1 \leq n \leq 500$。 - 子任务 2（30 分），$1 \leq n \leq 5000$。 - 子任务 3（40 分），$1 \leq n \leq3 \times 10^5$。 对于所有数据，$1 \leq n \leq3 \times 10^5$，$1\leq a_i \leq 10^9$。