UJGOI في كراكوف#406

UJGOI في كراكوف

ثانية
256 ميغابايت
Very hard

لقد وصلت إلى نهائيات UJGOI ! هناك n مشارك (المصنفين 1, 2, \dots, n) ويجب تعيين كل واحد منهم إلى واحدة من قاعات الدراسة المتاحة. رغما انه قد تم تعيين بعض المشاركين إلى قاعة دراسية، يجب عليك تخصيص قاعات دراسية للطلاب المتبقين. غير أنه، لتجنب تجميع عدد كبير من المشاركين المتقاربين في الترتيب معًا، يجب أن يحقق ترتيبك النهائي a_1, a_2, \dots, a_n (حيث 1\le a_i\le k هي قاعة الدراسة للمشارك ) الشروط التالية : يجب ألا تظهر أي قاعة دراسية تماما أكثر من \frac{r-\ell+1}{2} مرة في كل قطعة متصلة (مع 1 \le \ell < r \le n) — أي أنه لا توجد قاعة دراسية تحتوي على أغلبية الطلاب.

المطلوب منك هو تقديم حل يستوفي هذه المعايير.

Input

السطر الأول يحتوي على عدد صحيح واحد (1\le n\le 2\cdot 10^5) — عدد المشاركين.

السطر الثاني يحتوي على عدد صحيح واحد (1\le k\le 10^6) — عدد قاعات الدراسة المتاحة.

السطر الثالث يحتوي على عدد صحيح a_1,~a_2,\dots,~a_n (0\le a_i\le k) — ترتيب المشاركين حيث يعني a_i=0 أن قيمته لم تحدد بعد.

Output

في السطر الأول، أخرج "YES" إذا كان هناك ترتيب يحقق المطلوب و "NO" عكس ذلك.

إذا وجد ترتيب، فأخرج a_1,\dots, a_n المعدل في السطر الثاني.

Examples

Example 1

Loading
Loading

Example 2

Loading
Loading

Note

في المثال الأول، واحدة من التشكيلات الممكنة هي a=[1, 2, \underline{4}, \underline{3}, 1] . على سبيل المثال، إذا كانت \ell=1 و r=3، فإن [a_1, a_2, a_3]=a[1..3]=[1,2,4] تلبي الشرط، حيث يظهر كل عنصر مرة واحدة فقط، بينما \frac{r-\ell+1}{2}=\frac{3-1+1}{2}=1.5 > 1. يمكنك التحقق من أن الشرط محقق من أجل كل 1\le \ell < r\le n.

في المثال الثاني، يمكننا إثبات أنه لا يوجد تشكيلة تحقق الشرط. على سبيل المثال، إذا كانت التشكيلة هي a=[1, 2, \underline{3}, \underline{2}, 1]، فإن a[2..4]=[2, 3, 2] لا تحقق الشرط. حيث يوجد مشاركان في قاعة واحدة، ولكن \frac{r-\ell+1}{2}=1.5<2.

Scoring

  1. ( نقاط): a_i \geq 1;

  2. ( نقاط): a_i = 0;

  3. ( نقاط): لا يوجد i>1 بحيث a_i = a_{i-1} = 0;

  4. ( نقاط): k > 5;

  5. ( نقاط): k \le 5;

  6. ( نقاط): بدون قيود إضافية.