Énoncé du problème

Un membre de l'organisation JOI travaille dans un magasin de jouets. Aujourd'hui, il est chargé de ranger le rayon des peluches du magasin.

Sur l'étagère du rayon des peluches, $N$ peluches sont alignées de gauche à droite. L'étagère est divisée par des cloisons en $N$ compartiments, et l'on place $1$ peluche dans $1$ compartiment. Ce magasin de jouets vend au total $M$ types de peluches, numérotés respectivement de $1$ à $M$. Chacune des $N$ peluches alignées sur l'étagère appartient à l'un de ces $M$ types. De plus, il existe au moins $1$ peluche de chaque type.

Pour soigner la présentation, on souhaite réorganiser les peluches de sorte que toutes les peluches d'un même type soient placées de manière contiguë sur l'étagère. Il a été décidé de procéder de la façon suivante :

• Choisir certaines des $N$ peluches et les retirer de l'étagère. On ne déplace pas les peluches qui n'ont pas été retirées.
• Remettre les peluches retirées dans les compartiments libres de l'étagère, dans l'ordre souhaité.

Après le réarrangement, toutes les peluches d'un même type doivent se trouver consécutivement sur l'étagère. Écrivez un programme pour déterminer le nombre minimal de peluches à retirer afin de réaliser ce réarrangement.

Entrée

L'entrée se compose de $1 + N$ lignes.

Sur la ligne $1$ sont écrits $2$ entiers $N, M$ ($1 \le N \le 100000$, $1 \le M \le 20$) séparés par un espace, indiquant qu'il y a $N$ peluches et $M$ types de peluches.

Sur chacune des $N$ lignes suivantes est écrit un entier compris entre $1$ et $M$ inclus. L'entier écrit à la $i$-ème ligne ($1 \le i \le N$) parmi ces $N$ lignes représente le type de la peluche placée dans le $i$-ème compartiment en partant de la gauche de l'étagère. Pour chaque type, il est garanti qu'il existe au moins $1$ peluche.

Sortie

Affichez sur $1$ ligne le nombre minimal de peluches à retirer pour les réarranger.

Exemples d'entrée et de sortie

Exemple d'entrée 1

7 2
1
2
2
2
1
2
1

Exemple de sortie 1

2

Exemple d'entrée 2

12 4
1
3
2
4
2
1
2
3
1
1
3
4

Exemple de sortie 2

7

Dans l'exemple d'entrée 1, les types des peluches initialement placées sont, de gauche à droite, $1, 2, 2, 2, 1, 2, 1$. Pour minimiser le nombre de peluches à retirer lors du réarrangement, il suffit de retirer la $1$-ère et la $6$-ème peluche en partant de la gauche, puis de placer une peluche de type $2$ à la $1$-ère position depuis la gauche et une peluche de type $1$ à la $6$-ème position depuis la gauche. Dans ce cas, le nombre de peluches retirées est de $2$.