题目背景

译自 ROI 2018 Day2 T1. Расшифровка (Decryption)。

题目描述

研究表明，汉字的顺序并不一定能影响阅读。科学家们对数列进行了类似的研究。

给一个正整数数列，若数列首项为数列中所有数的最小值，末项为数列中的最大值，则我们称这是个正确的数列。例如，序列 $[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$。

输出格式

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

5
5 4 3 2 1

5

4
1 3 2 4

1

6
2 3 1 1 5 1

3

提示

对于 $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$。