کمینه نابه‌جایی


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

آرایه‌ی a1,a2,,ana_1, a_2, \dots, a_n\, از اعداد طبیعی وجود دارد. یک جایگشت p1,p2,,pnp_1, p_2, \cdots, p_n مناسب است اگر piaip_i \leq a_i به ازای تمامی اندیس‌های 1in1 \leq i \leq n برقرار باشد.

جایگشت مناسبی را پیدا کنید که تعداد نابه‌جایی‌های آن کمینه است. تعداد نابه‌جایی‌های جایگشت pp برابر با زوج اندیس‌های (i,j)(i, j) است که 1i<jn1 \leq i < j \leq n است و pi>pjp_i > p_j\, .

ورودی🔗

در خط اول ورودی عدد طبیعی nn می‌آید.

1n1000001 \leq n \leq 100 \, 000

در خط دوم اعداد طبیعی a1,a2,,ana_1, a_2, \cdots, a_n\, به‌ترتیب می‌آیند.

1ai1091 \leq a_i \leq 10^9

خروجی🔗

در تنها خط خروجی، جایگشت مناسبی که کمترین نابه‌جایی دارد را چاپ کنید. اگر چند جایگشت با این شرایط وجود داشت، یکی را به دلخواه چاپ کنید.

مثال‌ها🔗

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

5
5 5 5 2 2
Plain text

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

3 4 5 1 2
Plain text

جایگشت ارائه شده مناسب است. چون

  • p1=35=a1p_1 = 3 \leq 5 = a_1
  • p2=45=a2p_2 = 4 \leq 5 = a_2
  • p3=55=a3p_3 = 5 \leq 5 = a_3
  • p4=12=a4p_4 = 1 \leq 2 = a_4
  • p5=22=a5p_5 = 2 \leq 2 = a_5

و از بین تمام جایگشت‌های مناسب، این جایگشت کمترین تعداد نابه‌جایی را دارد.

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

1
964535797
Plain text

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

1
Plain text

تنها جایگشت یک عضوی 11 است که شرط مناسب بودن را هم دارد.

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

5
1 4 5 3 3
Plain text

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

1 4 5 2 3
Plain text

دو جایگشت 1,4,5,2,3\langle 1, 4, 5, 2, 3 \rangle و 1,4,5,3,2\langle 1, 4, 5, 3, 2 \rangle مناسب هستند که جایگشت اول نابه‌جایی کمتری دارد.