Sắp xếp z

Một dãy $a$ gồm $n$ phần tử được gọi là z-sorted nếu đồng thời thoả mãn hai điều kiện (chỉ số tính từ $1$):

1. $a_i\ge a_{i-1}$ với mọi chỉ số $i$ chẵn;
2. $a_i\le a_{i-1}$ với mọi chỉ số $i$ lẻ, $i>1$.

Nói cách khác, dãy phải đi lên rồi đi xuống xen kẽ: $a_1\le a_2\ge a_3\le a_4\ge \dots$

Ví dụ, các dãy $[1,2,1,2]$ và $[1,1,1,1]$ là z-sorted, còn $[1,2,3,4]$ thì không.

Cho dãy $a$, hãy sắp xếp lại (hoán vị) các phần tử của nó để thu được một dãy z-sorted, hoặc cho biết điều đó là không thể.

Dữ liệu vào

• Dòng đầu chứa số nguyên $n$ là số phần tử của dãy $a$.
• Dòng thứ hai chứa $n$ số nguyên $a_1,a_2,\dots ,a_n$.

Dữ liệu ra

Nếu có thể sắp xếp lại dãy $a$ thành một dãy z-sorted, in ra $n$ số nguyên cách nhau bởi dấu cách là dãy sau khi sắp xếp. Ngược lại, in ra đúng một từ Impossible.

Nếu có nhiều cách sắp xếp hợp lệ, in ra cách bất kỳ.

Ràng buộc

• $1\le n\le 1000$
• $1\le a_i\le {10}^9$

Ví dụ