给你一个长度为 $$$n$$$ 的排列 $$$p$$$ 和一个正整数 $$$k$$$。考虑长度为 $$$n$$$ 的排列 $$$q$$$,这样对于任何整数 $$$i$$$ 和 $$$j$$$,其中 $$$1 \le i < j \le n$$$,我们有 $$$$$$p_{q_i} \le p_{q_j} + k.$$$$$$
找出排列 $$$q$$$ 中可能的最小反转数。
排列是由从 $$$1$$$ 到 $$$n$$$ 的 $$$n$$$ 不同整数组成的数组,按任意顺序排列。例如,$$$[2,3,1,5,4]$$$ 是一个排列,但 $$$[1,2,2]$$$ 不是排列($$$2$$$ 在数组中出现两次),$$$[1,3,4]$$$ 也不是排列($$$n=3$$$ 但数组中有 $$$4$$$)。
排列 $$$a$$$ 中的反转是一对索引 $$$i$$$ 和 $$$j$$$ ($$$1 \le i, j \le n$$$),使得 $$$i < j$$$,但 $$$a_i > a_j$$$。
输入
第一行包含两个整数 $$$n$$$ 和 $$$k$$$ ($$$1 \le n \le 5000$$$, $$$1 \le k \le 8$$$)。
第二行包含 $$$n$$$ 不同的整数 $$$p_1, p_2, \ldots, p_n$$$ ($$$1 \le p_i \le n$$$)。
输出
打印排列 $$$q$$$ 中可能的最小反转数。
示例
输入 #1
1 1 1
输出 #1
0
输入 #2
3 1 2 3 1
输出 #2
1
输入 #3
5 2 5 4 3 2 1
输出 #3
6
输入#4
10 3 5 8 6 10 2 7 4 1 9 3
输出#4
18
注意
在第一个示例中,唯一的排列是 $$$q = [1]$$$ ($$$0$$$ 反转)。那么$$$p_{q_1} = 1$$$。
在第二个示例中,$$$1$$$ 反转的唯一排列是 $$$q = [1, 3, 2]$$$。那么$$$p_{q_1} = 2$$$,$$$p_{q_2} = 1$$$,$$$p_{q_3} = 3$$$。
在第三个示例中,$$$6$$$ 反转的可能排列之一是 $$$q = [3, 4, 5, 1, 2]$$$。那么$$$p_{q_1} = 3$$$、$$$p_{q_2} = 2$$$、$$$p_{q_3} = 1$$$、$$$p_{q_4} = 5$$$、$$$p_{q_5} = 4$$$。