#P18540. Swirly Sort

Swirly Sort

Swirly Sort

给定一个包含 nn 个整数的数组 AA,以及整数 kk(1≤k≤n1\le k\le n)。你希望把数组变成有序数组。

你可以执行任意多次下列两种操作:

  1. 选择 kk 个下标 1≤i1<i2<⋯<ik≤n1\le i_1<i_2<\cdots<i_k\le n,将这些位置上的值循环移动:原来的 A[i1]A[i_1] 移到位置 i2i_2,原来的 A[i2]A[i_2] 移到位置 i3i_3,依此类推,原来的 A[ik]A[i_k] 移到位置 i1i_1。所选下标必须按递增顺序排列。这次操作的费用为 00。
  2. 选择一个下标 ii,把 A[i]A[i] 增加 11 或减少 11。这次操作的费用为 11。

求使数组有序所需的最小总费用。

数组下标从 11 开始。这里“有序”指非降,即 X1≤X2≤⋯X_1\le X_2\le\cdots,允许相等元素。

输入格式

第一行包含整数 tt,表示测试用例数。

每个测试用例包含两行:第一行是整数 n,kn,k;第二行是数组初始值 A1,…,AnA_1,\ldots,A_n。

  • 1≤t≤1051\le t\le 10^5。
  • 1≤n≤3⋅1051\le n\le 3\cdot10^5。
  • 1≤k≤n1\le k\le n。
  • 1≤Ai≤1091\le A_i\le 10^9,这是数组初始值的限制。
  • 一份输入中,所有测试用例的 n⋅kn\cdot k 之和不超过 3⋅1053\cdot10^5。

输出格式

每个测试用例输出一行,一个整数,表示最小总费用。

完整原样例

输入:

4
4 1
6 4 3 7
4 2
6 4 3 7
4 3
6 4 3 7
4 4
6 4 3 7

输出:

3
0
1
2

原样例说明

四个测试用例的初始数组均为 [6,4,3,7][6,4,3,7]。

  • k=1k=1:将第一个元素减去 22,第三个元素加上 11,得到 [4,4,4,7][4,4,4,7],费用为 33。
  • k=2k=2:选择 i1=1,i2=3i_1=1,i_2=3,免费得到 [3,4,6,7][3,4,6,7],费用为 00。
  • k=3k=3:选择下标 1,2,31,2,3 循环移动,得到 [3,6,4,7][3,6,4,7];再对同样下标循环移动,得到 [4,3,6,7][4,3,6,7];最后把第一个元素减去 11,得到 [3,3,6,7][3,3,6,7]。总费用为 11。
  • k=4k=4:把第一个元素加上 11,得到 [7,4,3,7][7,4,3,7];把第二个元素减去 11,得到 [7,3,3,7][7,3,3,7];依次对全部四个位置循环移动三次,得到 [7,7,3,3][7,7,3,3]、[3,7,7,3][3,7,7,3]、[3,3,7,7][3,3,7,7]。总费用为 22。