Problema B - Recolorir a Cerca

Numa das muitas propriedades das Olimpíadas Nacionais de Informática há uma cerca a proteger a entrada. Esta cerca pode ser vista como um conjunto de N blocos colocados em linha, onde cada bloco está pintado de uma cor que é representada por um inteiro entre 1 e K. Um segmento colorido é um conjunto maximal de blocos consecutivos que têm todos a mesma cor. Sabe-se que cada segmento tem uma cor distinta, ou seja, não há dois segmentos com a mesma cor.

Parte I

São dadas as cores dos N blocos. Determina o número de segmentos.

Exemplo

Se N = 10, K = 10 e tivermos as seguintes cores:

Então há quatro segmentos:

Restrições:

São garantidos os seguintes limites em todos os casos de teste desta parte que irão ser colocados ao programa:

Os casos de teste desta parte do problema estão organizados num grupo:

Parte II

Para melhorar o aspeto da cerca, queremos repintar a cerca de forma a que o número de segmentos da cerca resultante seja no máximo X. Porém, pintar um bloco é custoso, por isso queremos minimizar o número de blocos que repintamos. Determina o número mínimo de blocos que precisamos de pintar.

Exemplo

Se N = 10, K = 10 e X = 2 e tivermos as seguintes cores:

Podemos repintar os blocos da seguinte forma para obter uma cerca com apenas 2 segmentos:

Neste caso só repintámos 3 blocos e não há forma de repintar menos, logo a resposta é 3.

Restrições:

São garantidos os seguintes limites em todos os casos de teste desta parte que irão ser colocados ao programa:

Os casos de teste desta parte do problema estão organizados em dois grupos:

Sumário de subtarefas

Os casos de teste do problema estão organizados em 3 grupos com restrições adicionais diferentes:

Input

A primeira linha contém um inteiro P, que representa a parte que o caso de teste representa. Se for 1, então o caso de teste refere-se à Parte I, se for 2 então refere-se à Parte II.

Na Parte I, segue-se uma linha com dois inteiros N, representando o número de blocos, e K, representando o número de cores.

Na Parte II, segue-se uma linha com três inteiros N, representando o número de blocos, K, representando o número de cores, e X, representando o número de segmentos objetivo.

Seguem-se um linha com N inteiros, que representam as cores da cerca.

Output

Parte I

O output deve conter uma linha contendo o número de segmentos.

Parte II

O output deve conter uma linha contendo o número mínimo de blocos a repintar.

Input do Exemplo 1

1
10 10
3 3 6 6 6 6 1 4 4 4

Output do Exemplo 1

4

Explicação do Exemplo 1

Este exemplo corresponde ao exemplo mencionado no enunciado da Parte I.

Input do Exemplo 2

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

Output do Exemplo 2

3

Explicação do Exemplo 2

Este exemplo corresponde ao exemplo mencionado no enunciado da Parte II.