Fabrique de jouets

Pour concrétiser votre rêve de devenir artiste, vous avez accepté un emploi de peintre dans une fabrique de jouets du fin fond de l'outback australien. Votre objectif : rejoindre dans la postérité des artistes de renom tels que Sidney NOLAN ou Brett WHITELEY. Malheureusement, dans cette entreprise, votre tâche n'est pas des plus prestigieuses... La fabrique est chargée de produire l'accessoire mondialement célèbre connu sous le nom de FLIP-FLAP. Il existe une vaste gamme de couleurs de flip-flaps différentes, chaque flip-flap étant intégralement peinte d'une couleur unie.

Votre poste de travail est situé à la sortie de la chaîne de production des flip-flaps. Vous recevez d'un côté les flip-flaps en attente de peinture, chacune devant être peinte d'une couleur donnée. De l'autre côté, vous disposez de C pots de peinture, un de chaque couleur. Votre désopilante tâche consiste à peindre chaque jouet avec la couleur adéquate.

Peindre une flip-flap est facile si le pot de peinture correspondant est déjà ouvert. Toutefois, si ce n'est pas le cas, vous devez mettre la main sur votre tournevis pour retirer le couvercle avant de peindre. De plus, la politique de l'entreprise vous interdit d'avoir plus de K pots de peinture ouverts simultanément, un excès de vapeurs de peinture pouvant susciter de sérieuses hallucinations. Ainsi, à partir du moment où vous avez exactement K pots ouverts, vous devez fermer l'un d'eux avant de pouvoir en ouvrir un autre. Tous les pots sont initialement fermés.

L'ouverture d'un pot étant une tâche fastidieuse, vous cherchez à en réaliser le moins possible. Étant données les couleurs des différentes flip-flaps et l'ordre dans lequel vous devez les peindre, votre objectif est de trouver le nombre minimal d'ouvertures de pots que vous aurez à effectuer pour peindre toutes les flip-flaps de la bonne couleur.

Tous les tests vérifient les contraintes suivantes :

• 1 <= N <= 100 000, où N est le nombre de flip-flaps à peindre.
• 1 <= C <= 100 000, où C est le nombre de pots, chaque pot étant d'une couleur différente.
• 1 <= K <= C, où K est le nombre maximum de pots pouvant être ouverts simultanément.

De plus, pour des tests correspondant à 50% des points :

• 1 <= N <= 1000.

Votre programme doit lire sur l'entrée standard. La première ligne de l'entrée contient les entiers N, C et K décrits ci-dessus. Les couleurs sont numérotées de 1 à C.

Les N lignes suivantes décrivent la couleur de chaque flip-flap, dans l'ordre dans lequel vous devez les peindre. Chaque ligne contiendra un entier c_i correspondant à la couleur de la i^e flip-flap à peindre (1 <= c_i <= C).

Votre programme doit écrire une seule ligne sur la sortie standard, comportant un unique entier : le nombre minimal d'ouvertures de pots nécessaires pour peindre toutes les flip-flaps.

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

6

Dans cet exemple, on dispose de quatre pots de peinture, et seuls deux d'entre eux peuvent être ouverts à la fois. Pour peindre les dix flip-flaps, voici une suite possible d'ouvertures et fermetures de pots :

Couleur	Pots ouverts	Action effectuée
3	3	Ouverture du pot 3.
4	3, 4	Ouverture du pot 4.
2	2, 3	Fermeture du pot 4, ouverture du pot 2.
2	2, 3
3	2, 3
4	3, 4	Fermeture du pot 2, ouverture du pot 4.
1	1, 4	Fermeture du pot 3, ouverture du pot 1.
4	1, 4
3	3, 4	Fermeture du pot 1, ouverture du pot 3.
4	3, 4

Cette suite nécessite six ouvertures de pots différentes, ce qui correspond au minimum réalisable.