Nel pianeta Wobniar ogni mattina splende un bellissimo e caratteristico arcobaleno.
La particolarità consiste nella disposizione dei colori, che possono presentarsi più volte all’interno dell’arco.
Il famoso artista Ed Esor decide un giorno di voler catturare lo splendore dell’arco in un collage di strisce colorate.
I suoi quadri sono valutati dalla critica in modo assai curioso.
Tra questi, i critici giudicano come migliori quelli costituiti da poche diverse strisce: per l’intellighenzia di Wobniar, usare poche strisce colorate è una tecnica sopraffina che fa della sovrapposizione un’arte.
Aiuta Ed Esor a minimizzare il numero di strisce del suo collage!
Se, ad esempio, l’arcobaleno fosse composto da sole 3 strisce di 2 colori diversi alternati, Ed Esor riuscirebbe a fare un collage usando due sole strisce di carta: una, disposta come base, dello stesso colore delle due strisce alle estremità dell’arcobaleno, l’altra posata sul centro della prima.
Dati in Input
Il file input.txt è composto da più numeri interi: sulla prima riga il numero N a indicare il numero di strisce dell’arcobaleno; sulla seconda riga sono posti N numeri interi C1, C2, …, CN a indicare i colori della striscia.
Ogni colore Ci è un numero intero compreso tra 0 e 255.
Strisce uniformi di colore sono indicate da più numeri uguali consecutivi.
Dati in Output
Il file output.txt dovrà contenere un unico numero: il numero minimo di strisce per riprodurre l’arcobaleno.
Assunzioni
- 0 < N ≤ 1000
- Per ogni Ci, 0 ≤ Ci ≤ 255
- Il tempo di esecuzione massimo è fissato in 4 secondi.
Esempi
| input.txt | output.txt | |
|---|---|---|
| 1 | 3 1 2 1 |
2 |
| 2 | 7 1 1 2 3 1 2 1 |
4 |