問題一覧 > 通常問題

No.711 競技レーティング単調増加

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 57
作問者 : しらっ亭しらっ亭 / テスター : koba-e964koba-e964
9 ProblemId : 1722 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2018-06-29 20:37:34

問題文

$N$ 要素の配列 $A$ があります。$A$ の $i$ 番目の要素は正整数 $A_i$ です。

$1$ 回の操作で $A$ の任意の要素を任意の正の整数に変更できます。

この操作を何度か行い、$A$ を狭義単調増加にしたいです。

$A$ を狭義単調増加に変更するのに必要な操作回数の最小値を求めて下さい。

$N$ 要素の配列 $A$ が狭義単調増加であるとは、$A_1 \lt A_2 \lt \dots \lt A_{N-1} \lt A_N$ であることを言います。

問題文(ストーリー付き)

しらっ亭君は競技プログラミングが趣味であり日夜コンテストに明け暮れています。競技プログラミングのコンテストにはレーティング値が付き物です。

しらっ亭君が $N$ 回のコンテストに参加した結果のレーティング値を時系列に記録した $N$ 要素の配列 $A$ があります。
$i$ 回目のコンテスト終了直後のレーティング値は $A_i$ です。

しらっ亭君はレーティング値が伸び悩んでいて悔しいので、この記録が狭義単調増加になるように記録を操作し改竄することにしました。

$1$ 回の操作では $N$ 個のレーティング値の記録のどれか $1$ つを選び、任意の正の整数に改竄することができます。
操作を何度か行い、レーティング値を時系列に見たときに狭義単調増加になっているように記録を改竄しようと思います。
必要な操作回数の最小値を求めて下さい。

レーティング値を時系列に見たときに狭義単調増加であるとは、$A_1 \lt A_2 \lt \dots \lt A_{N-1} \lt A_N$ であることを言います。

入力

$N$
$A_1$ $A_2$ $A_3$ $\dots$ $A_N$

$1 \le N \le 2 \times 10^5$
$1 \le A_i \le 10^9$
入力は全て整数

出力

答えを1行で出力してください。
最後に改行してください。

サンプル

サンプル1
入力
6
1 1 4 5 1 4
出力
3

例えば、$A_2, A_5, A_6$ の $3$ つを操作することで、$A$ を $\{1, 3, 4, 5, 10, 20\}$ のように狭義単調増加に変更できます。
なお、$A_2$ を変更しない $\{1, 1, 4, 5, 10, 20\}$ は狭義単調増加ではありません。

サンプル2
入力
9
333333333 111111111 444444444 111111111 555555555 999999999 222222222 666666666 555555555
出力
5

例えば、$5$ 回の操作で $\{100000000, 111111111, 444444444, 500000000, 555555555, 999999999, 1000000000, 1000000001, 1000000002\}$ にするのが最小回数です。
入力される $A$ の要素は最大でも $10^9$ ですが、操作後の値にはそのような制約は無いことに気をつけてください。

サンプル3
入力
20
99922 3916262 22 35176942 700 7841 2792958 812325 516 15108 68477 4892660 894 84778 1537710 31499 5844 93505127 493351 815
出力
12

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。