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:

  a_{i} ≥ a_{i} - 1 for all even i,  a_{i} ≤ a_{i} - 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 a_{i} (1 ≤ a_{i} ≤ 10^9) — the elements of the array a.


-----Output-----

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".


-----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

Difficulty: interview

Starter code:

Solutions:
n = int(input())
a = [int(i) for i in input().split()]
a.sort()
b = []
for i in range(n - 1, (n + 1) // 2 - 1, -1):
    b.append(a[i])
a = a[:(n + 1) // 2]
c = []
for i in range(len(b)):
    c.append(a[i])
    c.append(b[i])
if len(a) > len(b):
    c.append(a[-1])
print(*c)

n = int(input())
m = list(map(int, input().split()))
a = []
m.sort()
i = 0
j = len(m) - 1
while len(m) != len(a):
    if len(a) % 2 != 0:
        a.append(m[j])
        j -= 1
    else:
        a.append(m[i])
        i += 1
print(*a)

def solve():
    N = int(input())
    A = list(map(int, input().split()))

    A.sort()
    h = (N + 1) // 2
    f = A[:h]
    l = A[h:]

    ans = [0] * N

    for i in range(N):
        if i % 2 == 0:
            ans[i] = str(f[i//2])
        else:
            ans[i] = str(l[i//2])
    print(' '.join(ans))


def __starting_point():
    solve()

__starting_point()

n = int(input())
a = list(map(int, input().split()))
a.sort()
s = []
for i in range(0, len(a) // 2):
    s.append(a[i])
    s.append(a[len(a) - 1 - i])
if n % 2 == 1:
    s.append(a[len(a) // 2])

Po = 1
for k in range(2, len(s) - 1):
    if k % 2 == 1:
        if s[k] >= s[k - 1]:
            pass
        else:
            print('Impossible')
            Po = 0
            break
    elif k == 1:
        pass
    else:
        if s[k] <= s[k - 1]:
            pass
        else:
            print('Impossible')
            Po = 0
            break            
if Po == 1:
    print(' '.join(map(str, s)))

n = int(input())
l = list(map(int, input().split()))
l.sort(reverse = True)
mas = [0 for i in range(n)]
t = 0
for i in range(1, n, 2):
    mas[i] = l[t]
    t += 1
for i in range(0, n, 2):
    mas[i] = l[t]
    t += 1
print(*mas)

#! /usr/bin/env python3
'''
' Title:	
' Author:	Cheng-Shih, Wong
' Date:		
'''

import math

n = int(input())
a = [int(v) for v in input().split()]

a.sort()
half = math.ceil(n/2)
b = [0]*n

for i in range(0,half):
	b[i*2] = a[i]
for i in range(half,n):
	b[(i-half)*2+1] = a[i]

print( ' '.join([str(v) for v in b]) )


#!/usr/bin/env python3
# -*- coding: utf-8 -*-

import array


def z_sorted(length, sequence):
    sorted_sequence = sorted(sequence)
    answer = []
    for i in range(length // 2):
        answer.append(sorted_sequence[i])
        answer.append(sorted_sequence[length - i - 1])
    if length % 2 == 1:
        answer.append(sorted_sequence[length // 2])
    return answer


def main():
    length = int(input())
    sequence = array.array("L", list(map(int, input().split())))
    print(" ".join(map(str, z_sorted(length, sequence))))


def __starting_point():
    main()

__starting_point()

n = int(input())
s = list(map(int, input().split()))
s.sort()
p = n // 2
ans = [0] * (n)
q = n
for i in range(1, n, 2):
    q -= 1
    ans[i] = s[q]
for i in range(0, n, 2):
    q -= 1
    ans[i] = s[q]
print(*ans)

n=int(input())
ch=input()
d=ch.split()
for i in range(n):
    d[i]=int(d[i])
d.sort()
d1=[]
i=0
j=0
while j<n:
    d1.append(d[i])
    j+=1
    if j<n:
        j+=1
        d1.append(d[n-i-1])
    i+=1
B=False
for i in range(n):
    if d1[i]<d1[i-1] and (i+1)%2==0:
        B=True
    if d1[i]>d1[i-1] and (i+1)%2!=0:
        B=True
if B==False:
    for i in d1:
        print(i,end=" ")
else:
    print( "Impossible")


pocet = int(input())
pole = list(map(int, input().split()))

pole.sort()

boolean, pole2 = True, []
for i in range(len(pole)):
    if boolean:
        pole2.append(str(pole[i // 2]))
    else:
        pole2.append(str(pole[-(i//2 + 1)]))

    boolean = not boolean

print(' '.join(pole2))


from collections import deque

def z_sorted(a):
    a = deque(sorted(a))
    j = 0
    b = []
    
    while a:
        v = a.popleft() if (j%2 == 0) else a.pop()
        if j:
            if j%2 == 1:
                if v < b[-1]: return False
            else:
                if v > b[-1]: return False
        b.append(v)
        j += 1
    return b

def is_z_sorted(a):
    for i in range(len(a)):
        if i and i%2 == 1 and a[i] < a[i-1]: return False
        if i%2 == 0 and a[i] > a[i-1]: return False
    return True

def __starting_point():
    n = int(input())
    a = z_sorted([int(x) for x in input().split()])
    if a and is_z_sorted(a):
        print(' '.join(str(x) for x in a))
    else:
        print('IMPOSSIBLE')

__starting_point()

n = int(input())
ar = list(map(int, input().split()))
ar.sort()
for i in range(n // 2):
    print(ar[i], end=' ')
    print(ar[n - 1 - i], end=' ')
if n % 2 == 1:
    print(ar[n // 2])
    


n = int(input())
a = list(map(int,input().split()))
a.sort()
l = 0
k = (n+1)//2
for i in range((n+1)//2):
    print(a[l],end=' ')
    if k < n:
        print(a[k],end=' ')
    l += 1
    k += 1

n = int(input())

a = sorted(map(int, input().split()))

res = [10**18]

i = 0; j = n-1;
step = 0
while i <= j:
    if step == 0:
        res.append(a[i])
        i+=1
        if res[-1] > res[-2]:
            print("Impossible")
            break
    else:
        res.append(a[j])
        j-=1
        if res[-1] < res[-2]:
            print("Impossible")
            break
    step = step ^ 1
else:
    print(" ".join(map(str, res[1:])))
    


n = int(input())
a = sorted(map(int,input().split())) #List

for i in range(1, len(a)):
    if (i+1)%2 == 0:
        if a[i] < a[i-1]:
            temp = a[i]
            a[i] = a[i-1]
            a[i-1] = temp
            i = 1
    else:
        if a[i] > a[i-1]:
            temp = a[i]
            a[i] = a[i-1]
            a[i-1] = temp
            i = 1

for i in range(n):
    print(a[i], end=" ")
print()


n = int(input())
a = sorted(map(int,input().split())) #List

for i in range(1, len(a)):
    if (i+1)%2 == 0:
        if a[i] < a[i-1]:
            temp = a[i]
            a[i] = a[i-1]
            a[i-1] = temp
            #i = 1
    else:
        if a[i] > a[i-1]:
            temp = a[i]
            a[i] = a[i-1]
            a[i-1] = temp
            #i = 1

for i in range(n):
    print(a[i], end=" ")
print()


n = int(input())
a = sorted(map(int,input().split()))

for i in range(1, len(a)):
    if (i+1)%2 == 0:
        if a[i] < a[i-1]:
            temp = a[i]
            a[i] = a[i-1]
            a[i-1] = temp
    else:
        if a[i] > a[i-1]:
            temp = a[i]
            a[i] = a[i-1]
            a[i-1] = temp

for i in range(n):
    print(a[i], end=" ")
print()


n=int(input())
a=list(map(int,input().split()))
a.sort()
ans=[]
for i in range(n):
    if i%2==0:
        ans.append(str(a[i//2]))
    else:
        ans.append(str(a[-i//2]))



print(" ".join(ans))


def main():
    n = int(input())
    a, r = sorted(map(int, input().split())), [0] * n
    r[::2], r[1::2] = a[:n - n // 2], a[-1:n - n // 2 - 1:-1]
    print(' '.join(map(str, r)))


def __starting_point():
    main()

__starting_point()

n=int(input())
mas=[int(x) for x in input().split()]
mas.sort()
k=0
l=n-1
for i in range(n):
    if i&1:
        print(mas[l],end=' ')
        l-=1
    else:
        print(mas[k],end=' ')
        k+=1

N = int(input())
a = list(map(int, input().split()))
a.sort()

ans = []
for n in range(N):
	r = n//2
	if n % 2 == 0:
		x = a[r]
	else:
		x = a[N-1-r]
	ans.append(x)
print(' '.join(map(str, ans)))


n = int(input())
a = list(map(int,input().split()))

for i in range(n-1):
	if (i+1)%2==1:
		if a[i]>a[i+1]:
			t = a[i]
			a[i] = a[i+1]
			a[i+1] = t
		else:
			pass
	else:
		if a[i]<a[i+1]:
			t = a[i]
			a[i] = a[i+1]
			a[i+1] = t
		else:
			pass


for i in range(n):
	print(a[i], end = ' ')
	


3

n = int(input())
a = sorted([int(i) for i in input().split()])

i = 0
d = 1
s = n-1

while s >= 0:
	print(a[i], end=' ')
	i += d * s
	s -= 1
	d *= -1


n = int(input())
a = [int(x) for x in input().split(" ")]

a = sorted(a)

odd = n%2==1
l = a[:n//2+odd]
r = a[n//2+odd:]
r = r[::-1]

res = []
for i in range(n//2):
	res.append(l[i])
	res.append(r[i])
if odd:
	res.append(l[n//2])

print(" ".join([str(x) for x in res]))