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

اهالی شهر مهنه، علاقه بسیار زیادی به دریافت فایل از اینترنت داشتند. به همین دلیل سرعت بالای اتصال به اینترنت یکی از دغدغه‌های اصلی مردم این شهر بود و این باعث شده بود مردم شهر به دنبال سیم‌های مناسب برای انتقال با سرعت‌های بسیار بالا باشند. پس از تلاش‌های بسیار، مردم این شهر موفق شدند سیم‌های از جنس کدوتنبل بسازند که قابلیت انتقال با سرعت بالایی داشتند. در نتیجه پرورش کدوتنبل، به یکی از کارهای عادی تمام مردم شهر تبدیل شد.

پس از گذر سال‌ها، علاقه‌ی مردم به دریافت فایل از اینترنت از بین رفت و دیگر نیازی به کدوتنبل‌ها احساس نمی‌شد. در نتیجه مردم شهر تصمیم گرفتند کدوتنبل‌های خود را برای عموم به نمایش بگذارند. به همین منظور هریک از اهالی، کدوتنبل‌های خود را در خیابان اصلی شهر کنار یکدیگر قرار دادند.

در حال حاضر $n$ کدوتنبل در خیابان اصلی شهر مهنه قرار دارد و مسئول نمایشگاه می‌خواهد برای زیباسازی نمایشگاه، کدوتنبل‌ها را جابه‌جا کند. به علت سنگینی بیش از حد کدوتنبل‌ها ، مسئول نمایشگاه مجبور است برای جابه‌جا کردن آن ها از دستگاه خاصی استفاده کند. این دستگاه تنها وقتی می‌تواند جای دو کدوتنبل را با هم عوض کند که بزرگترین مقسوم‌علیه مشترک وزن این دو کدوتنبل، بزرگتر از یک باشد. در نتیجه برای مثال این دستگاه می‌تواند جای دو کدوتنبل با وزن‌های ۲ و ۴ را جابه‌جا کند. اما جابه‌جا کردن دو کدوتنبل با وزن‌های ۲ و ۳ با این دستگاه امکان‌پذیر نیست.

به ازای چینش خاصی از کدوتنبل‌ها در خیابان اصلی شهر، دنباله‌ی وزن این چینش، دنباله‌ای $n$ عضوی است که عضو $i$ام آن وزن کدوتنبل $i$ام در این چینش از سمت چپ است. مسئول نمایشگاه میخواهد طوری کدوتنبل‌ها را جابه‌جا کند که تعداد «نابه‌جایی»های دنباله‌ی وزن چینش نهایی کمینه شود. این چینش نهایی را «چینش زیبا» می‌نامیم.

برنامه‌ای بنویسید که با ورودی گرفتن دنباله‌ی وزن چینش اولیه‌ی کدوتنبل‌ها، دنباله‌ی وزن «چینش زیبا» را خروجی دهد.

ورودی

در خط اول ورودی عدد طبیعی $n$ تعداد کدوتنبل‌ها آمده است.

در خط دوم ورودی $n$ عدد $a_1,a_2, \cdots, a_n$ آمده‌اند که دنباله‌ی چینش اولیه‌ی کدوتنبل‌ها هستند. $$1 \leq n \leq 100\ 000$$

$$1 \leq a_i \leq 10^9$$

خروجی

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

زیرمسئله‌ها

مثال

ورودی نمونه ۱

4
3 4 2 9

خروجی نمونه ۱

3 2 4 9

ورودی نمونه ۲

3
9 2 3

خروجی نمونه ۲

3 2 9

ورودی نمونه ۳

4
6 2 4 6

خروجی نمونه ۳

2 4 6 6