洛谷的测试数据仅供民间交流使用,非官方测试数据。官方评测链接:https://www.cspro.org/。
是一个由 个自然数(非负整数)组成的数组。我们称其中 是一个非零段,当且仅当以下条件同时满足:
下面展示了几个简单的例子:
现在我们可以对数组 进行如下操作:任选一个正整数 ,然后将 中所有小于 的数都变为 。试选取一个合适的 ,使得数组 中的非零段个数达到最大。若输入的 所含非零段数已达最大值,可取 ,即不对 做任何修改。
从标准输入读入数据。
输入的第一行包含一个正整数 。
输入的第二行包含 个用空格分隔的自然数 。
输出到标准输出。
仅输出一个整数,表示对数组 进行操作后,其非零段个数能达到的最大值。
11 3 1 2 0 0 2 0 4 5 0 2
5
14 5 1 20 10 10 10 10 15 10 20 1 5 10 15
4
3 1 0 0
1
3 0 0 0
0
时,,5 个非零段依次为 、、、 和 ;此时非零段个数达到最大。
时,,4 个非零段依次为 、、 和 ;此时非零段个数达到最大。
时,,此时仅有 1 个非零段 ,非零段个数达到最大。
无论 取何值, 都不含有非零段,故非零段个数至多为 。
的测试数据满足 ;
全部的测试数据满足 ,且数组 中的每一个数均不超过 。