Vous avez atteint la finale de l'UJGOI ! Chacun des participants (classés 1, 2, \dots, n) doit être assigné à l'une des salles de classe disponibles. Bien que certains participants aient déjà été assignés à une salle de classe, vous devez assigner des salles pour les étudiants restants.
Cependant, pour éviter de regrouper trop de participants de rang similaire ensemble, votre arrangement final a_1, a_2, \dots, a_n (où 1\le a_i\le k est la salle de classe du -ème participant) doit satisfaire la condition suivante : Pour chaque segment contigu (avec 1 \le \ell < r \le n), il ne doit y avoir aucune salle de classe qui apparaît strictement plus de \frac{r-\ell+1}{2} fois — c'est-à-dire qu'il n'y a pas de salle de classe dans laquelle la majorité des étudiants est placée.
Votre tâche est de déterminer une assignation qui respecte ces critères.
La première ligne contient un entier (1\le n\le 2\cdot 10^5) — le nombre de participants.
La deuxième ligne contient un entier (1\le k\le 10^6) — le nombre de salles de classe disponibles.
La troisième ligne contient entiers a_1,~a_2,\dots,~a_n (0\le a_i\le k) — l'arrangement des participants où a_i=0 signifie que sa valeur n'est pas encore déterminée.
Dans la première ligne, affichez "YES" s'il existe un arrangement qui satisfait l'énoncé et "NO" sinon.
S'il existe un tel arrangement, alors affichez les a_1,\dots, a_n modifiés dans la deuxième ligne.
Example 1
Example 2
Dans le premier exemple, l'une des configurations possibles est a=[1, 2, \underline{4}, \underline{3}, 1]. Par exemple, si \ell=1 et r=3, alors [a_1, a_2, a_3]=a[1..3]=[1,2,4] satisfait la condition, puisque chaque élément apparaît une seule fois, et que \frac{r-\ell+1}{2}=\frac{3-1+1}{2}=1.5 > 1. Vous pouvez vérifier que la condition est respectée pour tous 1\le \ell < r\le n.
Dans le deuxième exemple, nous pouvons prouver qu'il n'existe aucune configuration satisfaisant la condition. Par exemple, si la configuration est a=[1, 2, \underline{3}, \underline{2}, 1], alors a[2..4]=[2, 3, 2] ne satisfait pas la condition. Deux participants sont dans une salle de classe, mais \frac{r-\ell+1}{2}=1.5<2.
( points): a_i \geq 1;
( points): a_i = 0;
( points): il n'y a pas i>1 tel que a_i = a_{i-1} = 0;
( points): k > 5;
( points): k \le 5;
( points): sans contraintes supplémentaires.