P16027 [CSPro 23] Non-zero Segment Partition

Luogu’s testdata are only for community exchange and are not official testdata. Official judging link: .

$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$.

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.

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$.

### 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