Ученик z-школы нашёл интересный способ сортировки чисел, называемый z-сортировкой. Массив a, состоящий из n элементов является z-отсортированным, если выполнены два условия:
- ai ≥ ai - 1 для всех чётных i,
- ai ≤ ai - 1 для всех нечётных i > 1.
Например массивы [1,2,1,2] и [1,1,1,1] являются z-отсортированными, а массив [1,2,3,4] таковым не является.
Можете ли вы осуществить z-сортировку заданного массива?
Выходные данные
Если возможно осуществить z-сортировку массива a выведите n целых чисел ai — элементы массива после z-сортировки. В противном случае выведите одно слово "Impossible".
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
1 2 2 1
|
1 2 1 2
|
|
2
|
5
1 3 2 2 5
|
1 5 2 3 2
|