logo AlgoBeat OnlineJudge
登录 注册

#216044. [CSPro 23] 非零段划分

内存限制:512 MiB 时间限制:1000 ms 标准输入输出
题目类型:VJudge(洛谷) 评测方式:VJudge
上传者: 匿名

题目描述

洛谷的测试数据仅供民间交流使用,非官方测试数据。官方评测链接:https://www.cspro.org/


是一个由 个自然数(非负整数)组成的数组。我们称其中 是一个非零段,当且仅当以下条件同时满足:

  • ;
  • 对于任意的整数 ,若 ,则 ;
  • ;

下面展示了几个简单的例子:

  • 中的 4 个非零段依次为
  • 仅有 1 个非零段;
  • 则不含非零段(即非零段个数为 )。

现在我们可以对数组 进行如下操作:任选一个正整数 ,然后将 中所有小于 的数都变为 。试选取一个合适的 ,使得数组 中的非零段个数达到最大。若输入的 所含非零段数已达最大值,可取 ,即不对 做任何修改。

输入格式

从标准输入读入数据。

输入的第一行包含一个正整数

输入的第二行包含 个用空格分隔的自然数

输出格式

输出到标准输出。

仅输出一个整数,表示对数组 进行操作后,其非零段个数能达到的最大值。

样例

样例输入 1

11
3 1 2 0 0 2 0 4 5 0 2

样例输出 1

5

样例输入 2

14
5 1 20 10 10 10 10 15 10 20 1 5 10 15

样例输出 2

4

样例输入 3

3
1 0 0

样例输出 3

1

样例输入 4

3
0 0 0

样例输出 4

0

数据范围与提示

样例 1 解释

时,,5 个非零段依次为 ;此时非零段个数达到最大。

样例 2 解释

时,,4 个非零段依次为 ;此时非零段个数达到最大。

样例 3 解释

时,,此时仅有 1 个非零段 ,非零段个数达到最大。

样例 4 解释

无论 取何值, 都不含有非零段,故非零段个数至多为

子任务

的测试数据满足

全部的测试数据满足 ,且数组 中的每一个数均不超过