جابجایی عریض


  • محدودیت زمان: ۵ ثانیه
  • محدودیت حافظه: ۲۵۶ مگابایت

به شما جایگشت p1,p2,...,pnp_1,p_2,...,p_n از اعداد ۱ تا nn داده شده است. شما می‌توانید عملیات زیر را به هر تعداد دلخواهی(حتی صفر) روی جایگشت انجام دهید.

  • دو عدد 1i<jn1\leq i < j \leq n انتخاب کنید که pipj=1\mid p_i-p_j \mid = 1 و KjiK \leq j - i.

بین تمام جایگشت‌هایی که از جایگشت اولیه می‌توان به آنها رسید کوچک‌ترین آنها از لحاظ لکسیکوگرافیکالی را پیدا کنید.

ورودی🔗

در خط اول ورودی دو عدد nn و KK به ترتیب داده شده‌اند. در خط دوم ورودی جایگشت p1,p2,...,pnp_1,p_2,...,p_n داده شده است. 1n500 0001\leq n \leq 500\ 000 1Kn11\leq K \leq n - 1

خروجی🔗

کوچکترین جایگشت از لحاظ لکسیکوگرافیکالی را در nn خط خروجی دهید.

مثال🔗

ورودی نمونه ۱🔗

4 2
4 2 3 1
Plain text

خروجی نمونه ۱🔗

2
1
4
3
Plain text

ورودی نمونه ۲🔗

5 1
5 4 3 2 1
Plain text

خروجی نمونه ۲🔗

1
2
3
4
5
Plain text

ورودی نمونه ۳🔗

8 3
4 5 7 8 3 1 2 6
Plain text

خروجی نمونه ۳🔗

1
2
6
7
5
3
4
8
Plain text