题目描述

$N$ 項からなる正整数列 $A\ =\ (A_1,\ A_2,\ \ldots,\ A_N)$ が与えられます。各 $A_i$ は $1,\ 2,\ \ldots,\ K$ のいずれかです。

あなたはこの数列に対して、次の操作を何度でも行うことができます：

• 隣接する $2$ 項を入れ替える。つまり、$|i-j|=1$ となる $i,\ j$ を選び、$A_i$ と $A_j$ を入れ替える。

数列 $A$ が以下の条件を満たすようにするために必要な操作回数の最小値を求めてください。

• 数列 $A$ は、連続部分列として $(1,\ 2,\ \ldots,\ K)$ を含む。 つまり、$A_n\ =\ 1$, $A_{n+1}\ =\ 2$, $\ldots$, $A_{n+K-1}\ =\ K$ が成り立つような $N-K+1$ 以下の正整数 $n$ が存在する。

输入格式

入力は以下の形式で標準入力から与えられます。

$N$ $K$ $A_1$ $A_2$ $\ldots$ $A_N$

输出格式

数列 $A$ が条件を満たすようにするために必要な操作回数の最小値を出力してください。

题目大意

给你一个有 $N$ 个正整数的序列 $A = (A_1,A_2,\dots,A_N)$，且 $A_i$ 是 $1,2,\dots$ 或 $K$。

你可以对这个序列做如下操作若干次。

• 交换两个相邻的元素，也就是选出 $i$ 和 $j$ 满足 $|i - j| = 1$ 并交换 $A_i$ 和 $A_j$。

找到最小的操作数使 $A$ 满足如下条件。

• $A$ 包含 $(1,2,\dots,K)$ 作为一个相接的子序列，也就是对于任意正整数 $n$ 最大是 $N - K + 1$ 满足 $A_n = 1, A_{n + 1} = 2,\dots,A_{N - K + 1} = K$。

4 3
3 1 2 1

2

5 5
4 1 5 2 3

5

8 4
4 2 3 2 4 2 1 4

5

提示

制約

• $2\leq\ K\leq\ 16$
• $K\ \leq\ N\leq\ 200$
• $A_i$ は $1,\ 2,\ \ldots,\ K$ のいずれかに等しい
• 数列 $A$ は、$1,\ 2,\ \ldots,\ K$ のそれぞれを少なくともひとつ含む

Sample Explanation 1

例えば次のように操作を行うのが最適です。 - $A_1$ と $A_2$ を入れ替える。$A$ は $(1,3,2,1)$ へ変化する。 - $A_2$ と $A_3$ を入れ替える。$A$ は $(1,2,3,1)$ へ変化する。 - $A_1\ =\ 1$, $A_2\ =\ 2$, $A_3\ =\ 3$ が成り立ち、条件を満たす。