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

---

باقر سرما خورده و مقادیر زیادی خسته‌ است.

باقر جایگشتی به طول \(n\) از اعداد ۱ تا \(n\) دارد که عناصر‌ آن را به ترتیب \(p_1, p_2, \ldots, p_n\) می‌نامیم.

امروز که باقر از خواب بلند شد، نگاهی به جایگشت انداخت و به این فکر افتاد که جایگشتش را تا جای ممکن زیباتر کند.

از نظر باقر جایگشت \(a\) از جایگشت \(b\) زیباتر است اگر و فقط اگر عددی مانند \(i\) وجود داشته باشد(\(1 \le i \le n\)) که به ازای تمامی \(k\)های طبیعی کوچک‌تر از \(i\) داشته باشیم \(a_k = b_k\) و همچنین به ازای \(i\)، \(a_i < b_i\).

باقر قرار است در \(n-1\) نوبت که از ۲ تا \(n\) شماره‌گذاری شده‌اند یک عملیات جابه‌جایی انجام دهد. در نوبت \(i\)اُم، او می‌تواند عنصر \(p_i\) را با \(p_{\lfloor\frac{i}{2}\rfloor}\) عوض کند یا کاری انجام ندهد. زیباترین جایگشتی که باقر می‌تواند با این جابه‌جایی‌ها به آن برسد را بیابید.

ورودی

در خط اول \(n\) آمده است. در خط دوم \(n\) عدد متمایز (از ۱ تا \(n\)) آمده‌است که به ترتیب عناصر جایگشت را مشخص می‌کنند.

\[1 \le n \le 1\ 000\]

خروجی

کوچکترین جایگشتی که باقر می‌تواند با این جابه‌جایی‌ها به آن برسد را چاپ کنید.

مثال

ورودی نمونه

5
5 3 1 2 4

خروجی نمونه

1 2 3 5 4

توضیح نمونه:

در این نمونه باقر باید عملیات جابه‌جایی را در جایگاه‌های دوم، سوم و چهارم انجام دهد.