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

پس از این که مافیای شهر نارهت توانست ساختار خود را بازسازی کند وقت آن رسیده است که اموالی که به ناحق به بعضی از اعضا رسیده بود بازپس گرفته شود و دوباره بین اعضا تقسیم شود. از چندین سال پیش مافیا برای تسلط کامل بر بازار شهر آپارتمانی در بالاترین طبقه تمام ساختمان‌های بازار اصلی شهر که همگی در یک خیابان قرار دارند را خریداری کرد و هر یک از اعضا را در یکی از آن‌ها اسکان داده بود. بازار اصلی در راستای شمال به جنوب قرار دارد و ارزش هر برج $i$ برابر تعداد ساختمان‌های $j$ای است که در سمت جنوب آن وجود دارند، ارتفاع کمتر از $i$ دارند و ارتفاع تمام ساختمان‌های بین $i$ و $j$ کمتر از ارتفاع $j$ است.

برای مثال در شکل زیر ارزش هر برج در بالای آن نوشته شده است.

حال وظیفه شما محاسبه ارزش هر ساختمان است تا مقدمات تقسیم آن‌ها بین اعضا فراهم شود.

ورودی

در خط اول $n$ که ($1 \leq n \leq 500\ 000$) تعداد ساختمان‌های موجود در بازار اصلی شهر می‌آید و سپس در خط بعد $n$ عدد می‌آید که به ترتیب ارتفاع جنوبی‌ترین ساختمان تا شمالی‌ترین ساختمان این بازار را نشان می‌دهد. ارتفاع هر ساختمان یک عدد طبیعی بین $1$ تا $2^{30}$ است.

خروجی

در خروجی باید به ازای هر ساختمان ارزش آن را چاپ کنید به عبارت دیگر در خروجی در یک سطر $n$ عدد بنویسید که به ترتیب ارزش جنوبی‌ترین ساختمان تا شمالی‌ترین ساختمان بازار است.

مثال

ورودی نمونه ۱

9
1 2 3 4 9 6 7 8 10

خروجی نمونه ۱

0 1 1 1 1 0 1 1 2