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())
lst = [int(bruh) for bruh in input().split()]

if n == 1 or n == 2:
    print(' '.join([str(bruhhhhh) for bruhhhhh in lst]))
    exit()

mid = n//2

lst.sort()
if n%2 == 0:
    evens = lst[mid:]
    odds = lst[:mid]
elif n%2 == 1:
    odds = lst[:mid+1]
    evens = lst[mid+1:]

res = []

for x in range(mid):
    res.append(odds[x])
    res.append(evens[x])

if n%2 == 1:
    res.append(odds[mid])
cnt = 0
for i in range(1, n-1):
    if i%2 == 0:
        if res[i-1] >= res[i] <= res[i+1]:
            cnt += 1

    elif i%2 == 1:
        if res[i-1] <= res[i] >= res[i+1]:
            cnt += 1

if cnt != n-2:
    print("Impossible")
    exit()

res1 = [str(bruhhhh) for bruhhhh in res]

print(' '.join(res1))
