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:
 1.  *a*<sub class="lower-index">*i*</sub> ≥ *a*<sub class="lower-index">*i* - 1</sub> for all even *i*, 1.  *a*<sub class="lower-index">*i*</sub> ≤ *a*<sub class="lower-index">*i* - 1</sub> for all odd *i* &gt; 1. 
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.

Can you make the array *z*-sorted?
The first line contains a single integer *n* (1 ≤ *n* ≤ 1000) — the number of elements in the array *a*.

The second line contains *n* integers *a*<sub class="lower-index">*i*</sub> (1 ≤ *a*<sub class="lower-index">*i*</sub> ≤ 10<sup class="upper-index">9</sup>) — the elements of the array *a*.
none
4
1 2 2 1
1 2 1 2
5
1 3 2 2 5
1 5 2 3 2
1
1
1
10
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
10
1 9 7 6 2 4 7 8 1 3
1 9 1 8 2 7 3 7 4 6
100
82 51 81 14 37 17 78 92 64 15 8 86 89 8 87 77 66 10 15 12 100 25 92 47 21 78 20 63 13 49 41 36 41 79 16 87 87 69 3 76 80 60 100 49 70 59 72 8 38 71 45 97 71 14 76 54 81 4 59 46 39 29 92 3 49 22 53 99 59 52 74 31 92 43 42 23 44 9 82 47 7 40 12 9 3 55 37 85 46 22 84 52 98 41 21 77 63 17 62 91
3 100 3 100 3 99 4 98 7 97 8 92 8 92 8 92 9 92 9 91 10 89 12 87 12 87 13 87 14 86 14 85 15 84 15 82 16 82 17 81 17 81 20 80 21 79 21 78 22 78 22 77 23 77 25 76 29 76 31 74 36 72 37 71 37 71 38 70 39 69 40 66 41 64 41 63 41 63 42 62 43 60 44 59 45 59 46 59 46 55 47 54 47 53 49 52 49 52 49 51
3
1 2 6
1 6 2
136
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
3
1 2 3
1 3 2
7
999999998 999999999 999999999 999999999 999999999 999999999 1000000000
999999998 1000000000 999999999 999999999 999999999 999999999 999999999
3
100 1 2
1 100 2
n = int(input())
massiv = list(map(int, input().split()))
for i in range(0, n - 1):
    if i % 2 == 0:
        if massiv[i] > massiv[i + 1]:
            massiv[i], massiv[i + 1] = massiv[i + 1], massiv[i]
    else:
        if massiv[i] < massiv[i + 1]:
            massiv[i], massiv[i + 1] = massiv[i + 1], massiv[i]
print(massiv)
