Almost Sorted

给定一个长度为 $n$ 的置换 $p$，以及一个正整数 $k$． 对于一个置换 $q$，要求对于所有满足 $1\leq i<j\leq n$ 的 $i,j$，有以下不等式成立： $$ p_{q_i}\leq p_{q_j}+k $$ 现在请求出满足条件的置换 $q$ 中，逆序对数最小的 $q$，它逆序对数是多少。 $1\leq n\leq 5000,1\leq k\leq 8$．

You are given a permutation $ p $ of length $ n $ and a positive integer $ k $ . Consider a permutation $ q $ of length $ n $ such that for any integers $ i $ and $ j $ , where $ 1 \le i < j \le n $ , we have $ $$$p_{q_i} \le p_{q_j} + k. $ $ </p><p>Find the minimum possible number of inversions in a permutation $ q $ .</p><p>A permutation is an array consisting of $ n $ distinct integers from $ 1 $ to $ n $ in arbitrary order. For example, $ \[2,3,1,5,4\] $ is a permutation, but $ \[1,2,2\] $ is not a permutation ( $ 2 $ appears twice in the array) and $ \[1,3,4\] $ is also not a permutation ( $ n=3 $ but there is $ 4 $ in the array).</p><p>An inversion in a permutation $ a $ is a pair of indices $ i $ and $ j $ ( $ 1 \\le i, j \\le n $ ) such that $ i &lt; j $ , but $ a\_i &gt; a\_j$$$.

The first line contains two integers $ n $ and $ k $ ( $ 1 \le n \le 5000 $ , $ 1 \le k \le 8 $ ). The second line contains $ n $ distinct integers $ p_1, p_2, \ldots, p_n $ ( $ 1 \le p_i \le n $ ).

Print the minimum possible number of inversions in the permutation $ q $ .

1 1
1

0

3 1
2 3 1

1

5 2
5 4 3 2 1

6

10 3
5 8 6 10 2 7 4 1 9 3

18

In the first example, the only permutation is $ q = [1] $ ( $ 0 $ inversions). Then $ p_{q_1} = 1 $ . In the second example, the only permutation with $ 1 $ inversion is $ q = [1, 3, 2] $ . Then $ p_{q_1} = 2 $ , $ p_{q_2} = 1 $ , $ p_{q_3} = 3 $ . In the third example, one of the possible permutations with $ 6 $ inversions is $ q = [3, 4, 5, 1, 2] $ . Then $ p_{q_1} = 3 $ , $ p_{q_2} = 2 $ , $ p_{q_3} = 1 $ , $ p_{q_4} = 5 $ , $ p_{q_5} = 4 $ .