No.1734 Decreasing Elements
Problem Statement
There is a sequence of non-negative integers $A = (A_1, A_2, \dots, A_N)$ with $N$ terms. Takahashi repeats the following operation until $A_i = 0$ holds for all $i = 1, 2, \dots, N$.
Operation:
- Among $i = 1, 2, \dots, N$, let $j$ be the smallest $i$ satisfying $A_i > 0$. Let $K$ be the value of $A_j$ at this time.
- For each of $i = j, j+1, \dots, N$, if $A_i \geq K$, replace $A_i$ with $A_i-K$. Otherwise, do nothing.
It can be proved that this process terminates after a finite number of operations. Find the number of operations Takahashi performs.
Input
$N$ $A_1\ A_2 \dots A_N$
- All inputs are integers.
- $1 \leq N \leq 2 \times 10^5$
- $0 \leq A_i \leq 2 \times 10^5$
Output
Print the answer on a single line.
Sample
Sample 1
Input
3 3 1 4
Output
2
The sequence $A$ changes through the operations as follows.
$(3, 1, 4)$ → $(0, 1, 1)$ → $(0, 0, 0)$
Therefore, the answer is $2$.
Sample 2
Input
1 0
Output
0
If all elements are $0$ from the beginning, no operation is performed.
Sample 3
Input
17 1 0 54 21 87 79 79 82 12 28 41 2 53 26 22 80 19
Output
10
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。
platinum
sak