Problem Description

Translated from COCI 2010.03.06 Task 4 “ZUMA”.

Mirko lines up $N$ marbles in a row, numbered $1 \ldots N$ in order. The color of marble $i$ is $c_i$. He discovered that if he touches $\ge K$ consecutive marbles and all of them have the same color, magic will make these marbles disappear; after that, the marbles before these $K$ marbles become adjacent to the marbles after these $K$ marbles.

Mirko has many marbles at home. He wants to insert as few marbles as possible among these $N$ marbles (he may also insert marbles before the first marble or after the last marble) so that all of the original $N$ marbles plus all inserted marbles disappear.

Input Format

The first line contains $N, K$.
The second line contains $c_1 \ldots c_N$.

Output Format

One line with one integer, the minimum number of marbles he needs to insert.

2 5
1 1

3

5 3
2 2 3 2 2

2

10 4
3 3 3 3 2 3 1 1 1 3

4

Hint

Constraints: $1 \le N \le 100$, $2 \le K \le 5$, $1 \le c_i \le 100$.

Translated by ChatGPT 5