#2847. 「ROI 2018 Day 2」抄本

内存限制:256 MiB 时间限制:500 ms 标准输入输出
题目类型:传统 评测方式:Special Judge
上传者: Planet6174

题目描述

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

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

样例

样例输入 1

5
5 4 3 2 1

样例输出 1

5

样例输入 2

4
1 3 2 4

样例输出 2

1

样例输入 3

6
2 3 1 1 5 1

样例输出 3

3

数据范围与提示

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