問題一覧 > 通常問題

No.1734 Decreasing Elements

レベル : / AI推定難易度 : 2350 / 実行時間制限 : 1ケース 3.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 30
作問者 : platinum / テスター : sak
お気に入りにしたユーザー ProblemId : 6775 / 自分の提出
問題文最終更新日: 2021-08-25 19:25:10
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 321 (順位表) の他の問題:

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もしくは右上の雲マークをクリックしてアカウントを作成してください。