非減少（ノンディクリース）化の必要性
n 個の整数で構成される配列が与えられています。この配列を、次の操作を 0 回以上行って「非減少」にすることを求められています。
任意のインデックス
i (1 ≤ a_i$$ を任意の整数に置き換えます。このとき、配列を非減少にするために必要な操作の回数をできるだけ少なくすることが目的です。
💡
厳密には、配列 が非減少とは、すべての (1 ≤ i < j ≤ n) について が成り立つことを指します。
入力
最初の行には、配列の長さを表す単一の整数
n (1 ≤ n ≤ 100 000) が与えられます。次の行には、
n 個の整数 (1 ≤ ≤ ) が空白区切りで与えられます。出力
配列を非減少にするのに必要な最小の操作回数を示す整数を 1 つ出力してください。
例
入力 | 出力 |
7
1 3 2 2 7 4 3 | 3 |
4
1 2 1 4 | 1 |
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB