题解

题面描述

我们有$n$块「记忆碎片」，它们按顺序排列，每块对应的记忆发生时间为$t_i$，且$t_1,t_2,\dots,t_n$构成$1$到$n$的一个排列。目标是将这些碎片重新排列成单调递增的顺序，也就是排序为$1,2,\dots,n$。允许的交换操作必须满足：

• 每次只能交换两块**发生时间相差不超过$k$**的碎片；
• 如果交换的两块碎片的记忆时间差恰好为$1$，则需要消耗$1$点精力（即代价$1$）；
• 如果交换碎片的记忆时间差大于$1$（但不超过$k$），则交换是免费的。

要求计算出在最优策略下恢复记忆所需消耗的最少精力。

题目内容

你得到了$n$块「记忆碎片」，它们排成一排，第$i$块碎片所对应记忆发生的时间为$t_i$;。t1,t2,...,tn是1到n的一个排列。

你希望重新排列这$n$块碎片，使它们单调递增(即重排为$1,2,...,n$) ，排列的规则为:

• 你有一个能力值$k$，每次你可以选择两块发生时间相差不超过$k$的碎片，交换它们的顺序;
• 由于发生时间过于靠近的两块碎片很难回想，对于两块发生时间相差恰好为$1$的碎片，交换它们需要消耗你$1$点精力;
• 对于发生时间相差大于$1$的碎片，交换它们则不需要耗费精力。

你想知道你最少需要消耗多少精力才能恢复你的「记忆」。

输入描述

第一行输入两个整数$n,k(4≦n≦2×10^5;1≦k≦n-1)$代表「记忆碎片」的个数、你的能力值。

第二行输入$n$个不同的整数$t_1,t_2,...,t_n (1≦t_i ≦n)$，其中，$t_i$代表第$i$块「记忆碎片」所对应记忆的发生时间。

输出描述

输出一个整数，表示你最少需要消耗的精力。

样例1

输入

4 1
2 1 3 4

输出

1

说明

在这个样例中，交换$t_1$和 $t_2$即可。我们可以证明，最少需要消耗$1$点精力。

样例2

输入

4 3
2 1 3 4

输出

0

说明

最优交换策略为:

• 交换$t_1$和$t_4$,得到{$4,1,3,2$};

• 交换$t_2$和$t_4$,得到{$4,2,3,1$};

• 交换$t_1$和$t_4$,得到{$1,2,3,4$}。

  至此，$t$已经有序，最少需要消耗$0$点精力。