- محدودیت زمان: ۱ ثانیه
- محدودیت حافظه: ۲۵۶ مگابایت
آرایهی a1,a2,…,an از اعداد طبیعی وجود دارد. یک جایگشت
p1,p2,⋯,pn
مناسب است اگر
pi≤ai
به ازای تمامی اندیسهای
1≤i≤n
برقرار باشد.
جایگشت مناسبی را پیدا کنید که تعداد نابهجاییهای آن کمینه است. تعداد نابهجاییهای جایگشت
p
برابر با زوج اندیسهای (i,j) است که
1≤i<j≤n
است و
pi>pj
.
ورودی🔗
در خط اول ورودی عدد طبیعی n میآید.
1≤n≤100000
در خط دوم اعداد طبیعی
a1,a2,⋯,an
بهترتیب میآیند.
1≤ai≤109
خروجی🔗
در تنها خط خروجی، جایگشت مناسبی که کمترین نابهجایی دارد را چاپ کنید. اگر چند جایگشت با این شرایط وجود داشت، یکی را به دلخواه چاپ کنید.
مثالها🔗
ورودی نمونه ۱🔗
خروجی نمونه ۱🔗
جایگشت ارائه شده مناسب است. چون
- p1=3≤5=a1
- p2=4≤5=a2
- p3=5≤5=a3
- p4=1≤2=a4
- p5=2≤2=a5
و از بین تمام جایگشتهای مناسب، این جایگشت کمترین تعداد نابهجایی را دارد.
ورودی نمونه ۲🔗
خروجی نمونه ۲🔗
تنها جایگشت یک عضوی 1 است که شرط مناسب بودن را هم دارد.
ورودی نمونه ۳🔗
خروجی نمونه ۳🔗
دو جایگشت ⟨1,4,5,2,3⟩ و ⟨1,4,5,3,2⟩ مناسب هستند که جایگشت اول نابهجایی کمتری دارد.