Problem
Ti viene data una striscia di carta a scacchi composta da n quadrati colorati numerati da 1 a n da sinistra a destra. Il quadrato i-esimo è inizialmente colorato c
i.
Diciamo che i quadrati i e j giacciono nella stessa componente se c
i = c
j e c
i = c
k per tutti i k che soddisfano i < k < J. In altre parole, tutti i quadrati del segmento da i a j devono avere lo stesso colore.
Ad esempio, la striscia [3,3,3] ha 1 componente connesso, mentre [5,2,4,4] ne ha 3.
Riempi il gioco viene riprodotto su questa striscia come segue:
All'inizio del gioco, scegli una casella di partenza casuale (questo non conta come turno).
Quindi, ad ogni mossa, cambi il colore del componente connesso contenente il quadrato iniziale con qualsiasi altro colore.
Scopri il numero minimo di mosse necessarie per ricolorare l'intera striscia in un unico colore.
Inserimento:
La prima riga contiene un singolo numero intero n (1 ≤ n ≤ 5000) — numero di quadrati.
La seconda riga contiene gli interi c
1,c
2,…,c
n (1 ≤ c
i > <5000) — i colori iniziali dei quadrati.
Uscita:
Stampa un singolo numero intero — il numero minimo di mosse da effettuare.
Esempi:
| Input |
Uscita |
4
5 2 2 1
| 2 |
8
4 5 2 2 1 3 5 5
| 4 |
1
4 |
0 |
Spiegazione:
Uno dei modi ottimali nel primo esempio: [5, 2, 2, 1] -> [5, 2, 2, 2] -> [5, 5, 5, 5]