D - Pure Straight Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 600 点

問題文

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 が存在する。

制約

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

入力

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

N K
A_1 A_2 \ldots A_N

出力

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

入力例 1

4 3
3 1 2 1

出力例 1

2

例えば次のように操作を行うのが最適です。

  • 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 が成り立ち、条件を満たす。

入力例 2

5 5
4 1 5 2 3

出力例 2

5

入力例 3

8 4
4 2 3 2 4 2 1 4

出力例 3

5

Score : 600 points

Problem Statement

Given is a sequence of N positive integers A = (A_1, A_2, \ldots, A_N), where each A_i is 1, 2, \ldots, or K.

You can do the following operation on this sequence any number of times.

  • Swap two adjacent elements, that is, choose i and j such that |i-j|=1 and swap A_i and A_j.

Find the minimum number of operations needed to make A satisfy the following condition.

  • A contains (1, 2, \ldots, K) as a contiguous subsequence, that is, there is a positive integer n at most N-K+1 such that A_n = 1, A_{n+1} = 2, \ldots, and A_{n+K-1} = K.

Constraints

  • 2\leq K\leq 16
  • K \leq N\leq 200
  • A_i is 1, 2, \ldots, or K.
  • A contains at least one occurrence of each of 1, 2, \ldots, K.

Input

Input is given from Standard Input in the following format:

N K
A_1 A_2 \ldots A_N

Output

Print the minimum number of operations needed to make A satisfy the condition.

Sample Input 1

4 3
3 1 2 1

Sample Output 1

2

One optimal sequence of operations is as follows.

  • Swap A_1 and A_2, changing A to (1,3,2,1).
  • Swap A_2 and A_3, changing A to (1,2,3,1).
  • Now we have A_1 = 1, A_2 = 2, A_3 = 3, satisfying the condition.

Sample Input 2

5 5
4 1 5 2 3

Sample Output 2

5

Sample Input 3

8 4
4 2 3 2 4 2 1 4

Sample Output 3

5