UJGOI Krakovda#406

UJGOI Krakovda

1 saniyə
256 meqabayt
Very hard

Siz UJGOI-nin finalına çatmısınız! iştirakçının (1, 2, \dots, n kimi sıralanmış) hər biri mövcud sinif otaqlarından birinə təyin edilməlidir. Bəzi iştirakçılar artıq hansısa sinif otağına təyin edilib, lakin siz qalan iştirakçılar üçün sinif otaqlarını təyin etməlisiniz.

Lakin, oxşar sıralara malik iştirakçıların çoxunu bir araya toplamaqdan qaçınmaq üçün, sizin yekun düzülüşünüz a_1, a_2, \dots, a_n (burada 1\le a_i\le k -ci iştirakçının sinif otağıdır) aşağıdakı şərti ödəməlidir: Hər bir ardıcıl seqment (burada 1 \le \ell < r \le n) üçün, heç bir sinif otağına \frac{r-\ell+1}{2}-dən ciddi çox sayda rast gəlinməməlidir — yəni, iştirakçıların əksəriyyətinin yerləşdirildiyi bir sinif otağı olmamalıdır.

Sizin tapşırığınız bu meyarlara cavab verən bir təyinatı müəyyən etməkdir.

Input

Birinci sətirdə bir tam ədəd (1\le n\le 2\cdot 10^5) — iştirakçıların sayı verilir.

İkinci sətirdə bir tam ədəd (1\le k\le 10^6) — mövcud sinif otaqlarının sayı verilir.

Üçüncü sətirdə tam ədəd a_1,~a_2,\dots,~a_n (0\le a_i\le k) — iştirakçıların yerləşməsi verilir. Burada a_i=0 onun dəyərinin hələ təyin edilmədiyini bildirir.

Output

Birinci sətirdə, əgər şərti ödəyən bir düzülüş varsa, "YES", əks halda "NO" çıxarın.

Belə bir düzülüş varsa, ikinci sətirdə dəyişdirilmiş a_1,\dots, a_n-i çıxarın.

Examples

Example 1

Loading
Loading

Example 2

Loading
Loading

Note

Birinci nümunədə mümkün düzülüşlərdən biri a=[1, 2, \underline{4}, \underline{3}, 1]-dir. Məsələn, əgər \ell=1 və r=3 olarsa, onda [a_1, a_2, a_3]=a[1..3]=[1,2,4] şərti ödəyir, çünki hər bir elementə yalnız bir dəfə rast gəlinir və \frac{r-\ell+1}{2}=\frac{3-1+1}{2}=1.5 > 1. Yoxlasanız, görə bilərsiniz ki, şərt bütün 1\le \ell < r\le n üçün ödənir.

İkinci nümunədə, şərti ödəyən bir düzülüşün olmadığını sübut edə bilərik. Məsələn, əgər düzülüş a=[1, 2, \underline{3}, \underline{2}, 1] olarsa, onda a[2..4]=[2, 3, 2] şərti ödəməz. İki iştirakçı bir sinif otağındadır, lakin \frac{r-\ell+1}{2}=1.5<2.

Scoring

  1. ( bal): a_i \geq 1;

  2. ( bal): a_i = 0;

  3. ( bal): elə i>1 yoxdur ki, a_i = a_{i-1} = 0 olsun;

  4. ( bal): k > 5;

  5. ( bal): k \le 5;

  6. ( bal): əlavə məhdudiyyətlər olmadan.