[R78E]递增 - 代码源竞赛平台

时空限制

1S/512M

题目描述

一台记录仪按时间顺序记录了 $n$ 次测量值 $a_1,a_2,\ldots,a_n$。整理记录时，需要将它们划分成若干段，让每一段的波动幅度比上一段更大。

你可以在相邻元素之间选择若干位置切开数组，将整个数组划分成若干个连续、非空的段。每个元素必须属于恰好一段，不能改变元素顺序。

一段的极差定义为该段最大元素与最小元素之差。只含一个元素的段，其极差为 $0$。

要求各段的极差从左到右严格递增。求最多可以分成多少段。只分成一段时，总是满足要求。

格式

输入格式

第一行包含一个正整数 $n$，为测量值的数量。

第二行包含 $n$ 个整数 $a_1,a_2,\ldots,a_n$，其中 $a_i$ 表示第 $i$ 次测量的数值。

输出格式

输出一个正整数，表示各段极差从左到右严格递增时，整个数组最多可以划分成的段数。

样例

样例输入 #1

5
7 7 8 5 10

样例输出 #1

3

样例解释 #1

可以分成 $[7]$、$[7,8]$、$[5,10]$，极差依次为 $0,1,5$。

四个段中至少有三个单元素段，它们的极差都为 $0$，不能严格递增，所以不能分成更多段。

样例输入 #2

6
1 2 3 4 5 6

样例输出 #2

3

样例解释 #2

可以分成 $[1]$、$[2,3]$、$[4,5,6]$，极差依次为 $0,1,2$。若分成四段，严格递增的非负整数极差至少为 $0,1,2,3$，在这个数组中对应的段长至少为 $1,2,3,4$，需要至少 $10$ 个元素。

样例输入 #3

4
4 4 4 4

样例输出 #3

1

样例解释 #3

任意段的极差都为 $0$，所以只能分成一段。

数据规模

注意：你只有通过了子任务的所有测试点，才能获得对应子任务的分数。

子任务编号	分数	$n\le$	特殊性质
$1$	$30$	$18$	无
$2$	$20$	$500$	A
$3$	$50$		无

特殊性质 A：数组 $a$ 为等差数列，即存在整数 $d$，使得对于所有 $1\le i<n$，都有 $a_{i+1}-a_i=d$。公差 $d$ 可以为 $0$ 或负数。

对于 $100\%$ 的数据，满足 $1\le n\le500$，$-10^9\le a_i\le10^9$，输入中的所有数都是整数。