P5189 [COCI 2009/2010 #5] ZUMA

**Translated from [COCI 2010.03.06](http://hsin.hr/coci/archive/2009_2010/) Task 4 “[ZUMA](http://hsin.hr/coci/archive/2009_2010/contest5_tasks.pdf)”.** 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.

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

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

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