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

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

باقر جایگشتی به طول $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

توضیح نمونه:

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