dd爱整齐

题号：NC221785
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

$dd$ 认为一个整齐的 $k$ 无限序列应该满足如下条件
如 $k=1$ 时 $……abababab……$
$k=2$ 时 $……abbabbabbabb……$
$k=3$ 时 $……abbbabbbabbbab……$
$k$ 有限序列为 $k$ 无限序列的任意连续子序列
以此类推，其中 $a,b$ 为正整数且 $a≥b$
如 $[2,1,1,1,2]，[6,10,6]$ 都可以认为是一个合法的 $k=3$ 的 $k$ 有限序列
现在给你一个序列 $c$ ，它不一定是一个 $k$ 有限序列，所以你可以对序列进行修正
对于每次修正，你可以选择一个位置 $i(1≤i≤n)$ ，把 $c[i]$ 变成 $c[i]-1$ ，问把该序列变成 $k$ 有限序列所需要的最小修正次数

输入描述:

第一行两个正整数n,k(1≤k≤n≤1000000),
第二行n个正整数描述序列c,对于序列中第i(1≤i≤n)个数c[i],满足1≤c[i]≤1000000000

输出描述:

一个数，表示最小修正次数

示例1

输入

复制

5 2
5 2 3 1 4

输出

复制

说明

改成[1,2,1,1,2]，最小修正次数为(5-1)+(2-2)+(3-1)+(1-1)+(4-2)=8