652B.md (1113B)
1 Source: https://codeforces.com/problemset/problem/652/B 2 3 B. z-sort 4 5 time limit per test 6 7 1 second 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 A student of *z*-school found a kind of sorting called *z*-sort. The array *a* with *n* elements are *z*-sorted if two conditions hold: 22 23 1. *a**i* ≥ *a**i* - 1 for all even *i*, 24 2. *a**i* ≤ *a**i* - 1 for all odd *i* > 1. 25 26 For example the arrays [1,2,1,2] and [1,1,1,1] are *z*-sorted while the array [1,2,3,4] isn’t *z*-sorted. 27 28 Can you make the array *z*-sorted? 29 30 Input 31 32 The first line contains a single integer *n* (1 ≤ *n* ≤ 1000) — the number of elements in the array *a*. 33 34 The second line contains *n* integers *a**i* (1 ≤ *a**i* ≤ 109) — the elements of the array *a*. 35 36 Output 37 38 If it's possible to make the array *a* *z*-sorted print *n* space separated integers *a**i* — the elements after *z*-sort. Otherwise print the only word "Impossible". 39 40 Examples 41 42 Input 43 44 ``` 45 4 46 1 2 2 1 47 ``` 48 49 Output 50 51 ``` 52 1 2 1 2 53 ``` 54 55 Input 56 57 ``` 58 5 59 1 3 2 2 5 60 ``` 61 62 Output 63 64 ``` 65 1 5 2 3 2 66 ```