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. ai ≥ ai - 1 for all even i, 
  2. ai ≤ ai - 1 for all odd i > 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?

Input

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 ai (1 ≤ ai ≤ 109) — the elements of the array a.

Output

If it's possible to make the array a z-sorted print n space separated integers ai — the elements after z-sort. Otherwise print the only word "Impossible".

Examples

Input

4
1 2 2 1


Output

1 2 1 2


Input

5
1 3 2 2 5


Output

1 5 2 3 2
n = int(input())
L = [int(s) for s in input().split()]
def zsort(l):
    if len(l) == 1:
        return l 
    if len(l) == 2:
        if l[0] > l[1]:
            return l[::-1]
        else:
            return l
    l1 = zsort(l[:2])
    l2 = zsort(l[2:])
    result = l1 + l2
    if result[1] < result[2]:
        result[1], result[2] = result[2], result[1]
    return result

result = [str(i) for i in zsort(L)]
print(' '.join(result))