2847 「ROI 2018 Day 2」抄本

译自 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]$。

需要编写一个程序，该程序按给定的顺序确定可以划分的最小正确段数。

对于 $30\%$ 的数据，$n⩽500;$
对于 $60\%$ 的数据，$n⩽5000;$
对于所有数据，$1 ⩽ n ⩽ 3\times 10^5,$ $1 ⩽ a_i ⩽ 10^9.$