Problem
On vous donne une bande de papier quadrillé composée de n carrés de couleur numérotés de 1 à n de gauche à droite. Le i-ème carré est initialement coloré c
i.
On dit que les carrés i et j appartiennent à la même composante si c
i = c
j et c
i = c
k pour tout k satisfaisant i < k < j. En d'autres termes, tous les carrés du segment de i à j doivent avoir la même couleur.
Par exemple, la bande [3,3,3] a 1 composant connexe, tandis que [5,2,4,4] en a 3.
Remplir le jeu se joue sur cette tranche comme suit :
Au début de la partie, vous choisissez une case de départ au hasard (cela ne compte pas comme un tour).
Ensuite, à chaque coup, vous changez la couleur du composant connecté contenant le carré de départ en n'importe quelle autre couleur.
Découvrez le nombre minimum de mouvements nécessaires pour recolorer toute la bande en une seule couleur.
Saisie :
La première ligne contient un seul entier n (1 ≤ n ≤ 5000) — nombre de carrés.
La deuxième ligne contient les entiers c
1,c
2,…,c
n (1 ≤ c
i <5000) — les couleurs initiales des carrés.
Sortie :
Imprimer un seul entier — le nombre minimum de coups à effectuer.
Exemples :
| Entrée |
Sortie |
4
5 2 2 1
| 2 |
8
4 5 2 2 1 3 5 5
| 4 |
1
4 |
0 |
Explication :
Une des manières optimales dans le premier exemple : [5, 2, 2, 1] -> [5, 2, 2, 2] -> ; [5, 5, 5, 5]