Background

Luogu’s testdata are only for community exchange and are not official testdata. Official judging link: https://www.cspro.org/.

Problem Description

$A_1, A_2, \cdots , A_n$ is an array of $n$ natural numbers (non-negative integers). We call $A_i, \cdots , A_j$ a non-zero segment if and only if all of the following conditions are satisfied at the same time:

• $1 \leq i \leq j \leq n$;
• For any integer $k$, if $i \leq k \leq j$, then $A_k > 0$;
• $i = 1$ or $A_{i-1} = 0$;
• $j = n$ or $A_{j+1} = 0$.

Some simple examples are shown below:

• In $A = [3, 1, 2, 0, 0, 2, 0, 4, 5, 0, 2]$, the 4 non-zero segments are $[3, 1, 2]$, $[2]$, $[4, 5]$, and $[2]$ in order;
• $A = [2, 3, 1, 4, 5]$ has only 1 non-zero segment;
• $A = [0, 0, 0]$ contains no non-zero segments (i.e., the number of non-zero segments is $0$).

Now we can perform the following operation on array $A$: choose any positive integer $p$, and then change all numbers in $A$ that are less than $p$ into $0$. Try to choose a suitable $p$ so that the number of non-zero segments in $A$ is maximized. If the number of non-zero segments in the input $A$ has already reached the maximum possible value, you may take $p = 1$, meaning no modification is made to $A$.

Input Format

Read input from standard input.

The first line contains a positive integer $n$.

The second line contains $n$ natural numbers $A_1, A_2, \cdots , A_n$, separated by spaces.

Output Format

Write output to standard output.

Output only one integer, which is the maximum number of non-zero segments that can be achieved after performing the operation on array $A$.

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

Hint

Explanation for Sample 1

When $p = 2$, $A = [3, 0, 2, 0, 0, 2, 0, 4, 5, 0, 2]$. The 5 non-zero segments are $[3]$, $[2]$, $[2]$, $[4, 5]$, and $[2]$ in order. At this time, the number of non-zero segments is maximized.

Explanation for Sample 2

When $p = 12$, $A = [0, 0, 20, 0, 0, 0, 0, 15, 0, 20, 0, 0, 0, 15]$. The 4 non-zero segments are $[20]$, $[15]$, $[20]$, and $[15]$ in order. At this time, the number of non-zero segments is maximized.

Explanation for Sample 3

When $p = 1$, $A = [1, 0, 0]$. At this time, there is only 1 non-zero segment $[1]$, and the number of non-zero segments is maximized.

Explanation for Sample 4

No matter what value $p$ takes, $A$ contains no non-zero segments, so the number of non-zero segments can be at most $0$.

Subtasks

$70\%$ of the testdata satisfy $n \leq 1000$.

All testdata satisfy $n \leq 5 \times 10^5$, and every number in array $A$ is at most $10^4$.

Translated by ChatGPT 5