#P2021092. 非零段划分

非零段划分

非零段划分

题目描述

题目描述

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

1≤i≤j≤n;

对于任意的整数k,若i≤k≤j,则Ak>0;

i=1或Ai−1=0;

j=n或Aj+1=0。

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

A=[3,1,2,0,0,2,0,4,5,0,2]中的4个非零段依次为[3,1,2]、[2]、[4,5]和[2];

A=[2,3,1,4,5]仅有1个非零段;

A=[0,0,0]则不含非零段(即非零段个数为0)。

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

输入格式

从标准输入读入数据。

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

输入的第二行包含n个用空格分隔的自然数A1,A2,⋯,An。

输出格式

输出到标准输出。

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

数据范围

(原站未提供,导入后需人工补齐)

样例

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

样例1解释
p=2时,A=[3,0,2,0,0,2,0,4,5,0,2],5个非零段依次为[3]、[2]、[2]、[4,5]和[2];此时非零段个数达到最大。
14
5 1 20 10 10 10 10 15 10 20 1 5 10 15
4

样例2解释
p=12时,A=[0,0,20,0,0,0,0,15,0,20,0,0,0,15],4个非零段依次为[20]、[15]、[20]和[15];此时非零段个数达到最大。
3
1 0 0
1

样例3解释
p=1时,A=[1,0,0],此时仅有1个非零段[1],非零段个数达到最大。
3
0 0 0
0

样例4解释
无论p取何值,A都不含有非零段,故非零段个数至多为0。

提示

子任务

70%的测试数据满足n≤1000;

全部的测试数据满足n≤5×10^5,且数组A中的每一个数均不超过10^4。