You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

阅读顺序

3个子任务，分别为30分，30分，40分

problem.pdf

sample.rar

阅读顺序

题目描述

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

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

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

输入格式

第一行一个正整数 $n$，第二行 $n$ 个正整数表示数列。

输出格式

输出一行，一个整数表示答案。

5
5 4 3 2 1

5

4
1 3 2 4

1

数据范围与评分

子任务1(30分)，$n\leq 500;$

对于 $60\%$ 的数据，$n \leq 5000;$

对于所有数据，$1 \leq n \leq 3\times 10^5,$ $1 \leq a_i \leq 10^9.$