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: EASY
Tags: Sorting
Skill types: Sorting

Starter code:

Solutions:
n = int(input())
a = [int(x) for x in input().split()]
a = sorted(a)
saida = []
for i in range(n):
	if i % 2 == 0:
		saida.append(a[i // 2])
	else:
		saida.append(a[n - 1 - i // 2])
print(*saida)


I = input
R = range
n = int(I())
l = n // 2
t = l + n % 2
a = sorted(map(int, I().split()))
b = []
for i in R(l):
	b += [a[i], a[i + t]]
if n % 2:
	b += [a[l]]
t = ' '.join(map(str, b))
for i in R(1, n):
	if i % 2 and b[i - 1] > b[i] or (i % 2 - 1 and b[i - 1] < b[i]):
		t = 'Impossible'
print(t)


n = int(input())
a = list(map(int, input().split()))
a.sort()
if len(a) % 2 != 0:
	list1 = a[1:len(a) // 2 + 1]
	list2 = a[len(a) // 2 + 1:len(a)]
	res = [[] for i in range(n)]
	res[0] = a[0]
	k1 = 0
	k2 = len(list2) - 1
if len(a) % 2 == 0:
	list1 = a[0:len(a) // 2]
	list2 = a[len(a) // 2:len(a)]
	res = [[] for i in range(n)]
	res[0] = a[0]
	k1 = 1
	k2 = len(list2) - 1
for i in range(2, len(a) + 1):
	if i % 2 != 0:
		res[i - 1] = list1[k1]
		k1 = k1 + 1
	if i % 2 == 0:
		res[i - 1] = list2[k2]
		k2 = k2 - 1
print(*res)


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
	elif 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())
l = list(map(int, input().split()))
l = sorted(l)
L = []
for i in range(n):
	if i % 2 == 0:
		L.append(l[i // 2])
	else:
		L.append(l[n - 1 - i // 2])
print(*L)


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', map(int, input().split()))
	print(' '.join(map(str, z_sorted(length, sequence))))
main()


a = int(input())
t = list(map(int, input().split()))
t.sort()
f = []
if a == 1:
	print(*t)
else:
	for k in range(1, a):
		if k % 2 != 0:
			f.append(t[(k - 1) // 2])
			t[(k - 1) // 2] = 0
		else:
			f.append(t[-(k // 2)])
			t[-(k // 2)] = 0
	f.append(sum(t))
	print(*f)


n = int(input())
a = sorted(list(map(int, input().split())))
ans = [0] * n
(left, right) = (0, n - 1)
for i in range(n):
	if i % 2 == 0:
		ans[i] = a[left]
		left += 1
	else:
		ans[i] = a[right]
		right -= 1
print(*ans)


_ = input()
a = sorted(map(int, input().split()))
i = 0
j = len(a) - 1
while i < j:
	print(a[i], a[j], end=' ')
	i += 1
	j -= 1
if i == j:
	print(a[i])


n = int(input())
n1 = list(map(int, input().split()))
n1.sort()
lst = []
k = 0
for i in range(n // 2):
	lst.append(n1[0])
	lst.append(n1[-1])
	n1.remove(n1[0])
	n1.remove(n1[-1])
if n1 != []:
	lst.append(n1[0])
for j in range(1, len(lst) - 1):
	if j - 1 == 0:
		continue
	elif j % 2 == 0:
		if lst[j - 1] >= lst[j - 2]:
			continue
		else:
			k = k + 1
			break
	elif lst[j - 1] <= lst[j - 2]:
		continue
	else:
		k = k + 1
		break
if k > 0:
	print('IMPOSSIBLE')
else:
	for j in lst:
		print(j, end=' ')


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


from math import ceil
n = int(input())
l = list(map(int, input().split()))
l.sort(reverse=True)
ans = [0] * n
for i in range(0, n // 2):
	ans[i * 2 + 1] = l[i]
for i in range(ceil(n / 2)):
	ans[2 * i] = l[n // 2 + i]
flag = True
for i in range(n):
	if i % 2 == 1:
		if not ans[i] >= ans[i - 1]:
			flag = False
			break
	elif i % 2 == 0 and i != 0:
		if not ans[i] <= ans[i - 1]:
			flag = False
if flag:
	print(*ans)
else:
	print('Impossible')


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


import sys
n = int(input())
a = [int(x) for x in input().split()]
a.sort()
b = [0] * (n + 1)
index = 0
for i in range(1, n + 1, 2):
	b[i] = a[index]
	index += 1
for i in range(2, n + 1, 2):
	b[i] = a[index]
	index += 1
for i in range(1, n + 1):
	if i % 2 == 0 and b[i] < b[i - 1]:
		print('Impossible')
		sys.exit(1)
	elif i % 2 == 1 and i > 1 and (b[i] > b[i - 1]):
		print('Impossible')
		sys.exit(1)
print(' '.join((str(x) for x in b[1:])))


import logging
import copy
import sys
logging.basicConfig(stream=sys.stderr, level=logging.DEBUG)

def solve(length, line):
	length = length[0]
	line.sort()
	r = [-1] * length
	for i in range(0, length, 2):
		r[i] = line[0]
		del line[0]
	line.sort(reverse=True)
	for i in range(1, length, 2):
		r[i] = line[0]
		del line[0]
	resultStr = ' '.join((str(e) for e in r))
	return resultStr

def main():
	firstLine = input().split()
	firstLine = list(map(int, firstLine))
	inputLines = input().split()
	inputLines = list(map(int, inputLines))
	print(solve(firstLine, inputLines))

def log(*message):
	logging.debug(message)
main()


t = int(input())
a = list(map(int, input().split()))[:t]
a.sort()
if t % 2 == 0:
	for i in range(len(a) // 2):
		print(a[i], end=' ')
		print(a[-i - 1], end=' ')
else:
	for i in range(len(a) // 2):
		print(a[i], end=' ')
		print(a[-i - 1], end=' ')
	print(a[len(a) // 2], end=' ')


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
			elif 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
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')


from sys import stdin
n = int(stdin.readline().strip())
nums = sorted([int(i) for i in stdin.readline().strip().split()])
(ans, flag) = ([nums[0]], True)
for i in range(1, n):
	idx = i // 2 if i % 2 == 0 else n - (i + 1) // 2
	ans.append(nums[idx])
	if i % 2 == 1:
		if ans[-1] < ans[-2]:
			flag = False
			break
	elif ans[-1] > ans[-2]:
		flag = False
		break
if flag:
	for i in ans:
		print(i, end=' ')
	print()
else:
	print('Impossible')


n = int(input())
A = list(map(int, input().split()))
A.sort()
B = []
for i in range((n - 1) // 2 + 1):
	if i == n - i - 1:
		B.append(A[i])
	else:
		B.append(A[i])
		B.append(A[n - i - 1])
b = True
for i in range(1, n):
	if (i + 1) % 2 == 0:
		if B[i] >= B[i - 1]:
			pass
		else:
			b = False
			break
	elif B[i] <= B[i - 1]:
		pass
	else:
		b = False
		break
if b:
	print(*B)
else:
	print('Impossible')


from collections import deque as de
import math
from collections import Counter as cnt
from functools import reduce
from typing import MutableMapping
from itertools import groupby as gb
from fractions import Fraction as fr

def factors(n):
	return set(reduce(list.__add__, ([i, n // i] for i in range(1, int(n ** 0.5) + 1) if n % i == 0)))

class My_stack:

	def __init__(self):
		self.data = []

	def my_push(self, x):
		return self.data.append(x)

	def my_pop(self):
		return self.data.pop()

	def my_peak(self):
		return self.data[-1]

	def my_contains(self, x):
		return self.data.count(x)

	def my_show_all(self):
		return self.data

	def isEmpty(self):
		return len(self.data) == 0
arrStack = My_stack()

def decimalToBinary(n):
	return bin(n).replace('0b', '')

def isPrime(n):
	if n <= 1:
		return False
	if n <= 3:
		return True
	if n % 2 == 0 or n % 3 == 0:
		return False
	i = 5
	while i * i <= n:
		if n % i == 0 or n % (i + 2) == 0:
			return False
		i = i + 6
	return True

def get_prime_factors(number):
	prime_factors = []
	while number % 2 == 0:
		prime_factors.append(2)
		number = number / 2
	for i in range(3, int(math.sqrt(number)) + 1, 2):
		while number % i == 0:
			prime_factors.append(int(i))
			number = number / i
	if number > 2:
		prime_factors.append(int(number))
	return prime_factors

def get_frequency(list):
	dic = {}
	for ele in list:
		if ele in dic:
			dic[ele] += 1
		else:
			dic[ele] = 1
	return dic

def Log2(x):
	return math.log10(x) / math.log10(2)

def isPowerOfTwo(n):
	return math.ceil(Log2(n)) == math.floor(Log2(n))

def ceildiv(x, y):
	return (x + y - 1) // y

def di():
	return map(int, input().split())

def li():
	return sorted(list(map(int, input().split())))
n = int(input())
a = li()
if n % 2:
	kmax = a[n // 2 + 1:]
	kmin = a[:n // 2 + 1]
	ans = []
	for i in range(n):
		if (i + 1) % 2:
			ans.append(kmin[i // 2])
		else:
			ans.append(kmax[i // 2])
	print(*ans)
else:
	kmax = a[n // 2:]
	kmin = a[:n // 2]
	ans = []
	for i in range(n):
		if (i + 1) % 2:
			ans.append(kmin[i // 2])
		else:
			ans.append(kmax[i // 2])
	print(*ans)


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))
solve()


def main(n, a):
	a1 = sorted(a)
	a2 = list(reversed(sorted(a)))
	r = []
	for i in range(n // 2):
		r.append(a1[i])
		r.append(a2[i])
	if n % 2 == 1:
		r.append(a1[n // 2])
	return ' '.join(list(map(str, r)))
print(main(int(input()), list(map(int, input().split(' ')))))


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


import re
import sys
exit = sys.exit
from bisect import bisect_left as bsl, bisect_right as bsr
from collections import Counter, defaultdict as ddict, deque
from functools import lru_cache
cache = lru_cache(None)
from heapq import *
from itertools import *
from math import inf
from pprint import pprint as pp
enum = enumerate
ri = lambda : int(rln())
ris = lambda : list(map(int, rfs()))
rln = sys.stdin.readline
rl = lambda : rln().rstrip('\n')
rfs = lambda : rln().split()
cat = ''.join
catn = '\n'.join
mod = 1000000007
d4 = [(0, -1), (1, 0), (0, 1), (-1, 0)]
d8 = [(-1, -1), (0, -1), (1, -1), (-1, 0), (1, 0), (-1, 1), (0, 1), (1, 1)]
n = ri()
a = ris()
a.sort()
for i in range(2, n, 2):
	(a[i - 1], a[i]) = (a[i], a[i - 1])
print(*a)


def main():
	input()
	numbers = list(map(int, input().split()))
	numbers = sorted(numbers)
	n = len(numbers)
	result = [0 for _ in range(n)]
	j = 0
	k = n - 1
	for i in range(len(result)):
		if i % 2 == 1:
			result[i] = numbers[k]
			k -= 1
		else:
			result[i] = numbers[j]
			j += 1
	result = [str(el) for el in result]
	print(' '.join(result))
main()


import math
from math import floor
number = int(input())
array = input().split()
nArray = []
for i in array:
	nArray.append(int(i))
nArray.sort()
oddArray = nArray[0:math.ceil(number / 2)]
evenArray = nArray[math.ceil(number / 2):number]
resultArray = []
for i in range(0, int(number / 2)):
	resultArray.append(oddArray[i])
	resultArray.append(evenArray[i])
if number % 2 != 0:
	resultArray.append(oddArray[int(number / 2)])
String = ''
for i in resultArray:
	String += str(i) + ' '
print(String)


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

def solve(a):
	a.sort()
	if len(a) < 3:
		return ' '.join(map(str, a))
	mid = len(a) // 2 + 1
	(x, y) = (a[:mid], a[mid:][::-1])
	for (i, j) in enumerate(y):
		x.insert(2 * i + 1, j)
	return ' '.join(map(str, x))
print(solve(arr))


def main():
	n = int(input())
	l = sorted(map(int, input().split()))
	res = [0] * n
	(res[::2], res[1::2]) = (l[:n - n // 2], l[:-(n // 2) - 1:-1])
	print(*res)
main()


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())
a = list(map(int, input().split()))
a.sort()
b = list(reversed(a))
c = a + b
c[::2] = a
c[1::2] = b
c = c[:len(c) // 2]
for i in c:
	print(i, sep=' ', end=' ')


n = int(input())
arr = list(map(int, input().split()))
arr = sorted(arr)
for i in range(1, n):
	if i % 2 == 1 and i != n - 1:
		(arr[i], arr[i + 1]) = (arr[i + 1], arr[i])
print(*arr)


n = int(input())
array = list(map(int, input().split()))
array.sort()
ans = []
for i in range(n // 2):
	ans.append(array[i])
	ans.append(array[n - i - 1])
if len(array) % 2 != 0:
	ans.append(array[n // 2])
print(' '.join([str(i) for i in ans]))


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


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
	elif 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=' ')


n = int(input())
ls = list(map(int, input().split()))
ls.sort()
i = 0
j = len(ls) - 1
lsN = []
while i <= j:
	if i < j:
		lsN.append(ls[i])
		lsN.append(ls[j])
	elif i == j:
		lsN.append(ls[i])
	i = i + 1
	j = j - 1
s = ''
for i in range(n):
	if i < n - 1:
		s = s + str(lsN[i]) + ' '
	elif i == n - 1:
		s = s + str(lsN[i])
print(s)


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


n = int(input())
odd = 0
even = n // 2
z = sorted(list(map(int, input().split())))
if n % 2 != 0:
	even += 1
f = even
while odd < f:
	print(z[odd], end=' ')
	if even < n:
		print(z[even], end=' ')
	odd += 1
	even += 1


n = int(input())
A = sorted(map(int, input().split()))
B = [0] * n
B[::2] = A[:(n + 1) // 2]
B[1::2] = A[(n + 1) // 2:]
print(*B)


n = int(input())
a = list(map(int, input().split()))
a.sort()
l = n // 2 + 1 if n % 2 else n // 2
j = 0
q = True
for i in range(n):
	if q:
		print(a[j], end=' ')
		q = False
		j += 1
	else:
		print(a[l], end=' ')
		q = True
		l += 1


import sys
input = sys.stdin.readline
n = int(input())
unsort = list(map(int, input().strip().split()))
unsort.sort()
for i in range(n // 2):
	print(unsort[i], end=' ')
	print(unsort[i + (n - 1) // 2 + 1], end=' ')
if n % 2 == 1:
	print(unsort[n // 2])


import sys
n = int(input())
arr = list(map(int, input().split()))
arr.sort()
answer = [0] * 1001
answer[0] = arr[0]
i = 1
j = n - 1
iterx = 1
while iterx < n:
	if (iterx + 1) % 2 == 0:
		answer[iterx] = arr[j]
		j = j - 1
		if answer[iterx] < answer[iterx - 1]:
			print('Impossible')
			sys.exit()
	else:
		answer[iterx] = arr[i]
		i = i + 1
		if answer[iterx] > answer[iterx - 1]:
			print('Impossible')
			sys.exit()
	iterx = iterx + 1
for diggy in range(0, n):
	print(answer[diggy])


n = int(input())
arr = list(map(int, input().split()))
arr.sort()
ans = []
i = 0
while len(ans) < n:
	if i % 2 == 0:
		ele = arr.pop(0)
		ans.append(ele)
	else:
		ele = arr.pop(-1)
		ans.append(ele)
	i += 1
print(*ans)


n = int(input())
a = list(sorted(map(int, input().split())))
ret = list()
i = 0
j = n - 1
while i <= j:
	if i != j:
		ret.append(a[i])
	ret.append(a[j])
	i += 1
	j -= 1
can = True
for i in range(1, n, 2):
	if ret[i] < ret[i - 1]:
		can = False
if can:
	print(' '.join(map(str, ret)))
else:
	print('Impossible')


n = int(input())
q = [int(x) for x in input().split()]
i = 0
j = n - 1
q.sort()
while i <= j:
	print(q[i], end=' ')
	i += 1
	if i <= j:
		print(q[j], end=' ')
		j -= 1
print()


n = int(input())
list = sorted(map(int, input().split(' ')))
half = n // 2
first_half = list[:half]
second_half = list[half:]
second_half = second_half[::-1]
for i in range(0, half):
	print(first_half[i], end=' ')
	print(second_half[i], end=' ')
else:
	if n % 2 == 1:
		print(second_half[-1])


num = int(input())
ans = ''
z_sort = [int(i) for i in input().split()]
z_sort.sort()
z_small = z_sort[:-(-num // 2)]
z_big = z_sort[-(-num // 2):]
if len(z_sort) % 2 == 0:
	for i in range(len(z_small)):
		ans += str(z_small[i]) + ' '
		ans += str(z_big[i]) + ' '
	ans = ans[:-1]
else:
	for i in range(len(z_small) - 1):
		ans += str(z_small[i]) + ' '
		ans += str(z_big[i]) + ' '
	ans += str(z_small[-1])
print(ans)


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)


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 = sorted(map(int, input().split()))
for i in range(2, n, 2):
	(a[i - 1], a[i]) = (a[i], a[i - 1])
print(*a)


from sys import stdin
n = int(stdin.readline())
a = list(map(int, stdin.readline().split()))
a.sort()
half = int(len(a) / 2)
if len(a) % 2 == 1:
	half += 1
odd = sorted(a[:half])
even = sorted(a[half:], reverse=True)
l = zip(odd, even)
next_ind = 0
next_left = 1
while 1:
	if next_left:
		if next_ind >= len(odd):
			break
		print(odd[next_ind], '', end='')
	else:
		if next_ind >= len(even):
			break
		print(even[next_ind], '', end='')
		next_ind += 1
	next_left = 1 - next_left


n = int(input())
x = list(map(int, input().split()))
x.sort()
index = 0
index2 = 0
m = []
check = 0
for i in range(n):
	if i % 2 == 1:
		m.append(x[n - index - 1])
		if i != n - 1 and m[i] < m[i - 1]:
			check = -1
			break
		index += 1
	else:
		m.append(x[index2])
		if i != 0 and m[i] > m[i - 1]:
			check = -1
			break
		index2 += 1
if check == 0:
	for i in range(n - 1):
		print(m[i], end=' ')
	print(m[n - 1])
else:
	print('Impossible')


nums = int(input())
list_num = input().split()
for num in range(int(nums)):
	list_num[num] = int(list_num[num])
list_num.sort()
result = ''
start = 0
end = nums - 1
for n in range(int(nums)):
	if n % 2 == 0:
		result += str(list_num[start]) + ' '
		start += 1
	else:
		result += str(list_num[end]) + ' '
		end += -1
print(result)


n = int(input())
val = list(map(int, input().split()))
res = [0] * n
val = sorted(val)
for i in range(1, n + 1):
	if i & 1:
		res[i - 1] = val[i // 2]
	else:
		res[i - 1] = val[n - i // 2]
print(*res)


n = int(input())
a_list = list(map(int, input().split()))
a_list = sorted(a_list)
a_list.reverse()
i = 0
j = 1
ans_arr = [0] * len(a_list)
while j < n:
	ans_arr[j] = a_list[i]
	i += 1
	j += 2
j = 0
while j < n:
	ans_arr[j] = a_list[i]
	i += 1
	j += 2
for i in range(0, len(ans_arr)):
	print(ans_arr[i], end=' ')


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


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


n = int(input())
a = list(map(int, input().split()))
a.sort()
results = [None] * n
half_len = n // 2
for i in range(half_len):
	results[i * 2] = a[i]
for i in range(half_len):
	results[i * 2 + 1] = a[~i]
if n % 2 == 1:
	results[-1] = a[half_len]
print(' '.join(map(str, results)))


def fv(v, n):
	nv = n * [0]
	m = (n + 1) // 2
	for c in range(m):
		nv[2 * c] = v[c]
	s = v[m:][::-1]
	for c in range(n - m):
		nv[2 * c + 1] = s[c]
	return nv
n = int(input())
v = [int(c) for c in input().split()]
v.sort()
for c in fv(v, n):
	print(c, end=' ')


n = int(input())
array = input().split(' ')
MaxArray = []
for i in range(n):
	array[i] = int(array[i])
for i in range(n // 2):
	MaxArray.append(max(array))
	array.remove(max(array))
if n % 2 != 0:
	print(array[0], end=' ')
	array.remove(array[0])
	for i in range(n // 2):
		print(MaxArray[n // 2 - 1 - i], array[i], end=' ')
else:
	for i in range(n // 2):
		print(array[i], MaxArray[n // 2 - 1 - i], end=' ')


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


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


n = int(input())
a = sorted(list(map(int, input().split())))
ans = [0] * n
i = 0
while 2 * i < n:
	ans[2 * i] = a[i]
	i += 1
j = 0
while 2 * j + 1 < n:
	ans[2 * j + 1] = a[i]
	i += 1
	j += 1
print(*ans)


(n, a) = (int(input()), list(sorted(map(int, input().split()))))
b = [0] * n
b[::2] = a[0:(n + 1) // 2]
b[1::2] = list(reversed(a[(n + 1) // 2:]))
print(*b)


n = int(input())
a = list(map(int, input().split()))
a.sort()
b = [0 for x in range(n)]
for i in range(int((n + 1) / 2)):
	b[i * 2] = a[i]
for i in range(int(n / 2)):
	b[i * 2 + 1] = a[n - i - 1]
for i in range(n):
	print(b[i])


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)


a = int(input())
b = input()
b = b.split(' ')
b = map(int, b)
b = list(b)
for i in range(1, len(b), 2):
	if b[i] < b[i - 1]:
		t = b[i - 1]
		b[i - 1] = b[i]
		b[i] = t
for i in range(2, len(b), 2):
	if b[i] > b[i - 1]:
		t = b[i - 1]
		b[i - 1] = b[i]
		b[i] = t
v = b.copy()
for i in range(1, len(b), 2):
	if b[i] < b[i - 1]:
		t = b[i - 1]
		b[i - 1] = b[i]
		b[i] = t
if v == b:
	v = map(str, v)
	print(' '.join(v))
else:
	print('Impossible')


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


n = int(input())
n2 = (n + 1) // 2
L = sorted(map(int, input().split()))
R = L[:]
(R[::2], R[1::2]) = (L[:n2], L[n2:][::-1])
print(' '.join(map(str, R)))


l = int(input())
n = list(map(int, input().split()))
n.sort()
ans = []
i = 0
while len(ans) < l:
	ans.append(n[i])
	ans.append(n[l - i - 1])
	i = i + 1
ans = ans[:l]
print(*ans)


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 = list(map(int, input().split()))
a.sort()
l = []
for i in range(n):
	if i % 2 == 0:
		x = min(a)
		l.append(x)
		a.remove(x)
	else:
		y = max(a)
		l.append(y)
		a.remove(y)
for r in l:
	print(r, end=' ')


n = int(input())
a = map(int, input().split())
a = sorted(a)
b = []
for i in range(n // 2):
	b.append(a[i])
	b.append(a[n - 1 - i])
if len(a) % 2:
	b.append(a[n // 2])
print(*b)


import sys
input = sys.stdin.readline
n = int(input())
k = list(map(int, input().split()))
k.sort()
bigs = k[n // 2 + 1:]
smalls = k[:n // 2 + 1]
string = ''
while len(smalls) != 0:
	try:
		cat = str(bigs.pop(0)) + ' '
	except:
		cat = ''
	string += str(smalls.pop(0)) + ' ' + cat
print(string)


n = int(input())
x = [int(q) for q in input().split()]
y = sorted(x)
z = []
if n & 1 == 0:
	for i in range(0, n // 2):
		z.append(y[i])
		z.append(y[n - i - 1])
	print(*z)
else:
	for i in range(0, 1 + n // 2):
		z.append(y[i])
		z.append(y[n - i - 1])
	z.pop()
	print(*z)


class CodeforcesTask652BSolution:

	def __init__(self):
		self.result = ''
		self.n = 0
		self.array = []

	def read_input(self):
		self.n = int(input())
		self.array = [int(x) for x in input().split(' ')]

	def process_task(self):
		self.array.sort()
		result = []
		for x in range(self.n // 2):
			result.append(self.array[x])
			result.append(self.array[x + self.n // 2 + self.n % 2])
		if self.n % 2:
			result.append(self.array[self.n // 2])
		self.result = ' '.join([str(x) for x in result])

	def get_result(self):
		return self.result
Solution = CodeforcesTask652BSolution()
Solution.read_input()
Solution.process_task()
print(Solution.get_result())


import math
import sys

def scan():
	return list(map(int, sys.stdin.readline().strip().split()))

def solution():
	n = int(input())
	a = scan()
	b = []
	c = []
	a.sort()
	for i in range(n // 2):
		b.append(a[i])
	for j in range(n // 2, n):
		c.append(a[j])
	j = 0
	c.reverse()
	for i in range(n // 2 + 1):
		if i < len(b):
			print(b[i], end=' ')
		if i < len(c):
			print(c[i], end=' ')
solution()


def zSorted(anArr):
	for k in range(1, len(anArr), 2):
		if anArr[k] < anArr[k - 1]:
			return False
	for k in range(2, len(anArr), 2):
		if anArr[k] > anArr[k - 1]:
			return False
	return True
numOfelems = int(input())
arrayA = [int(x) for x in input().split()]
if zSorted(arrayA):
	print(' '.join([str(x) for x in arrayA]))
else:
	for i in range(1, len(arrayA), 2):
		if arrayA[i] < arrayA[i - 1]:
			(arrayA[i - 1], arrayA[i]) = (arrayA[i], arrayA[i - 1])
	for i in range(2, len(arrayA), 2):
		if arrayA[i] > arrayA[i - 1]:
			(arrayA[i - 1], arrayA[i]) = (arrayA[i], arrayA[i - 1])
	if zSorted(arrayA):
		print(' '.join([str(x) for x in arrayA]))
	else:
		print('Impossible')


import sys
from bisect import bisect_right as rb
from collections import deque
from queue import PriorityQueue
from math import *
input_ = lambda : sys.stdin.readline().strip('\r\n')
ii = lambda : int(input_())
il = lambda : list(map(int, input_().split()))
ilf = lambda : list(map(float, input_().split()))
ip = lambda : input_()
fi = lambda : float(input_())
ap = lambda ab, bc, cd: ab[bc].append(cd)
li = lambda : list(input_())
pr = lambda x: print(x)
prinT = lambda x: print(x)
f = lambda : sys.stdout.flush()
mod = 998244353
n = ii()
a = il()
b = sorted(a)
ans = [0 for i in range(n)]
j = 0
for i in range(0, n, 2):
	ans[i] = b[j]
	j += 1
for i in range(1, n, 2):
	ans[i] = b[j]
	j += 1
print(*ans)


num1 = int(input())
list1 = sorted(map(int, input().split()))
i = 0
j = num1 - 1
list2 = []
while j > i:
	list2.append(list1[i])
	list2.append(list1[j])
	i += 1
	j -= 1
if i == j:
	list2.append(list1[j])
for i in list2:
	print(i, end=' ')


x = int(input())
L = [i for i in input().split()]
L.sort(key=int)
L2 = []
for i in range(len(L)):
	if i % 2 == 0:
		L2.append(L[0])
		L.pop(0)
	else:
		L2.append(L[-1])
		L.pop(-1)
S = ' '.join(L2)
print(S)


n = int(input())
a = list(map(int, input().split()))
a.sort()
if n <= 2:
	for i in a:
		print(i, end=' ')
	exit()
b = a[:n // 2]
a = a[n // 2:]
a.reverse()
for i in range(n - 1):
	if i % 2 == 0:
		print(b[i // 2], end=' ')
	else:
		print(a[i // 2], end=' ')
if n % 2 == 0 or n == 3:
	print(a[-1])
else:
	print(b[-1])


n = int(input())
a = [int(x) for x in input().split()]
a.sort()
i = 0
j = n - 1
while i < j:
	print(a[i], end=' ')
	print(a[j], end=' ')
	i += 1
	j -= 1
if n % 2:
	print(a[i])


n = int(input())
arr = sorted(list(map(int, input().split())))
odd = [arr[i] for i in range(1, n, 2)]
even = [arr[i] for i in range(0, n, 2)]
ans = []
for i in range(1, n + 1):
	if i % 2 != 0:
		ans.append(arr[0])
		arr.pop(0)
	else:
		ans.append(arr[-1])
		arr.pop(-1)
print(*ans)


n = int(input(''))
lis = [int(x) for x in input().split(' ')]
lis.sort()
for j in range(n):
	for i in range(0, n - j - 1):
		if i % 2 == 1 and lis[i + 1] >= lis[i]:
			(lis[i], lis[i + 1]) = (lis[i + 1], lis[i])
final = []
for p in lis:
	final.append(str(p))
print(' '.join(final))


a = int(input())
b = [int(i) for i in input().split()]
b = sorted(b)
firstHalf = b[:(a + 1) // 2]
secondHalf = b[(a + 1) // 2:]
newList = []
for i in range(a):
	if i % 2 == 0:
		newList.append(firstHalf[i // 2])
	else:
		newList.append(secondHalf[i // 2])
for var in newList:
	print(var, end=' ')


n = int(input())
a = list(map(int, input().split()))
k = []
a.sort()
for i in range((n + 1) // 2):
	k.append(a[i])
	a.reverse()
	k.append(a[i])
	a.reverse()
if n % 2 == 1:
	k.pop()
print(*k)


a = int(input())
b = sorted(map(int, input().split()))
i = 0
while i < a // 2:
	print(b[i], b[-i - 1], end=' ')
	i += 1
if a % 2:
	print(b[a // 2])


n = int(input())
a = list(map(int, input().split()))
a.sort()
b = a[len(a) - len(a) // 2:]
a = a[:len(a) - len(b)]
answ = ''
i = 0
while i < n:
	answ += str(a[i // 2])
	answ += ' '
	i += 1
	if i < n:
		answ += str(b[i // 2])
	answ += ' '
	i += 1
print(answ)


from math import floor
from math import sqrt
from math import ceil
from itertools import combinations, accumulate, groupby, count
from sys import stdout, stdin, setrecursionlimit
from io import BytesIO, IOBase
from collections import *
from random import *
from bisect import *
from string import *
from queue import *
from heapq import *
from math import *
from os import *
from re import *

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = read(self._fd, max(fstat(self._fd).st_size, 8192))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = read(self._fd, max(fstat(self._fd).st_size, 8192))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(stdin, stdout) = (IOWrapper(stdin), IOWrapper(stdout))

def fast():
	return stdin.readline().strip()

def zzz():
	return [int(i) for i in fast().split()]
(z, zz) = (fast, lambda : list(map(int, z().split())))
(szz, graph, mod, szzz) = (lambda : sorted(zz()), {}, 10 ** 9 + 7, lambda : sorted(zzz()))

def lcd(xnum1, xnum2):
	return xnum1 * xnum2 // gcd(xnum1, xnum2)

def output(answer, end='\n'):
	stdout.write(str(answer) + end)
dx = [-1, 1, 0, 0, 1, -1, 1, -1]
dy = [0, 0, 1, -1, 1, -1, -1, 1]
n = int(z())
arr = szzz()
ans = [0] * n
(left, right) = (0, n - 1)
for i in range(n):
	if i % 2 == 0:
		ans[i] = arr[left]
		left += 1
	else:
		ans[i] = arr[right]
		right -= 1
res = True
if res:
	print(*ans)
else:
	print('Impossible')


n = int(input())
r = lambda : list(map(int, input().split()))
arr = r()
arr.sort()
x = arr[:(n + 1) // 2]
y = arr[(n + 1) // 2:]
for (i, j) in zip(x, y):
	print(i, j, end=' ')
if n % 2:
	print(x[-1])


n = int(input())
a = [int(_) for _ in input().split()]
a.sort()
na = []
for i in range(len(a)):
	if i % 2 == 0:
		na.append(a.pop(0))
	else:
		na.append(a.pop(-1))
print(' '.join(map(str, na)))


n = int(input())
a = sorted(map(int, input().split(' ')))
ans = [0] * n
for i in range(n):
	ans[i] = a[i // 2] if i % 2 == 0 else a[(i + n) // 2]
print(' '.join(map(str, ans)))


N = int(input())
X = sorted(list(map(int, input().split())))
(i, j) = (0, N - 1)
(Step, Check) = (0, True)
Answer = []
while Step != N:
	if Check:
		Answer.append(X[i])
		i += 1
	else:
		Answer.append(X[j])
		j -= 1
	Check = not Check
	Step += 1
print(*Answer)


__metaclass__ = type
__author__ = 'xdlove'
n = int(input())
lt = list(map(int, input().split()))
lt.sort()
res = list()
n += 1
for i in range(n // 2):
	res.append(lt[i])
	if i + n // 2 == n - 1:
		break
	res.append(lt[i + n // 2])
print(' '.join(map(str, res)))


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


n = int(input())
numero = input().split()
for i in range(n):
	numero[i] = int(numero[i])
if n == 1:
	print(numero[0])
else:
	for i in range(1, n):
		if i % 2 != 0 and numero[i] < numero[i - 1]:
			auxiliar = numero[i]
			numero[i] = numero[i - 1]
			numero[i - 1] = auxiliar
		elif i % 2 == 0 and numero[i] > numero[i - 1]:
			auxiliar = numero[i]
			numero[i] = numero[i - 1]
			numero[i - 1] = auxiliar
	respuesta = str(numero[0])
	for i in range(1, n):
		respuesta = respuesta + ' ' + str(numero[i])
	print(respuesta)


import sys

def read_data():
	n = int(next(sys.stdin).strip())
	numbers = list(map(int, next(sys.stdin).split()))
	return numbers

def solve(numbers):
	N = len(numbers)
	numbers.sort()
	(lN, rN) = (numbers[:(N + 1) // 2], numbers[(N + 1) // 2:])
	ans = [0] * N
	for i in range((N + 1) // 2):
		ans[2 * i] = lN[i]
		if 2 * i + 1 < N:
			ans[2 * i + 1] = rN[i]
	return ans
print(*solve(read_data()))


n = int(input()) - 1
a = sorted([int(x) for x in input().split(' ')])
for i in range(n):
	print(a[int((n + i + 1 if i % 2 else i) / 2)], end=' ')
print(a[n if n % 2 else int(n / 2)])


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


n = int(input())
l = list(map(int, input().split()))
for i in range(n):
	if i % 2 == 0:
		if l[i] >= l[i - 1]:
			(l[i], l[i - 1]) = (l[i - 1], l[i])
	elif l[i] <= l[i - 1]:
		(l[i], l[i - 1]) = (l[i - 1], l[i])
print(*l)


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


n = int(input())
s = [int(x) for x in input().split()]
s.sort()
q = [s[n // 2]] * n
for i in range(n // 2):
	q[2 * i] = s[i]
	q[2 * i + 1] = s[n - i - 1]
print(' '.join(map(str, q)))


a = int(input())
b = sorted(list(map(int, input().split())))
c = []
for i in range(a):
	if i % 2 == 0:
		c.append(b.pop(0))
	else:
		c.append(b.pop(-1))
print(' '.join(map(str, c)))


length = int(input())
numbers = sorted(map(int, input().split()))
half = length // 2
for i in range(half):
	print(numbers[i], numbers[-i - 1], sep=' ', end=' ')
if length - 2 * half:
	print(numbers[half])


def L2():
	n = int(input())
	arr = [int(x) for x in input().split()]
	arr.sort()
	zsort = []
	for i in range(n):
		if i % 2 == 0:
			zsort.append(min(arr))
			arr.remove(min(arr))
		else:
			zsort.append(max(arr))
			arr.remove(max(arr))
	flag = False
	for i in range(1, n):
		if i % 2 == 0:
			if zsort[i - 2] <= zsort[i - 1] >= zsort[i]:
				continue
			else:
				print('Impossible')
				flag = True
				break
	if flag == False:
		for i in zsort:
			print(i, end=' ')
L2()


n = int(input())
a = list(map(int, input().split()))
a.sort()
l = 0
r = n - 1
while l < r:
	print(a[l], a[r], end=' ')
	l += 1
	r -= 1
if l == r:
	print(a[l])


n = int(input())
a = sorted(list(map(int, input().split())))
i = 0
j = n - 1
b = []
for k in range(n):
	if k % 2 == 1:
		b.append(a[j])
		j -= 1
	else:
		b.append(a[i])
		i += 1
print(*b)


n = int(input())
l = sorted(list(map(int, input().split())))
x = l[:(n + 1) // 2]
y = l[(n + 1) // 2:]
i = 0
while len(x) != 0 or len(y) != 0:
	if i % 2 == 0:
		print(x[0], end=' ')
		x.pop(0)
	else:
		print(y[0], end=' ')
		y.pop(0)
	i += 1


n = int(input())
xs = sorted([int(x) for x in input().split()])
r = [0] * n
for i in range(0, n, 2):
	r[i] = xs[i // 2]
	if i != n - 1:
		r[i + 1] = xs[-(i // 2 + 1)]
print(*r)


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


import sys
n = int(input())
a = sorted(map(int, input().split()))
ans = [0] * n
j = 0
for i in range(n + 1 >> 1):
	ans[j] = a[i]
	j += 2
j = 1
for i in range(n + 1 >> 1, n):
	ans[j] = a[i]
	j += 2
print(*ans)


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)


def zsort(n, A):
	A.sort()
	return [A[-(i + 1) // 2] if i % 2 else A[i // 2] for i in range(n)]

def main():
	n = readint()
	A = readintl()
	print(' '.join(map(str, zsort(n, A))))
import sys

def readint():
	return int(input())

def readinti():
	return map(int, input().split())

def readintl():
	return list(readinti())

def readintll(k):
	return [readintl() for _ in range(k)]

def log(*args, **kwargs):
	print(*args, **kwargs, file=sys.stderr)
main()


n = int(input())
inp = list(map(int, input().split()))
srt = sorted(inp)
ans = []
if n % 2 == 0:
	for i in range(n // 2):
		ans.append(str(srt[i]))
		ans.append(str(srt[-(i + 1)]))
	print(' '.join(ans))
else:
	for i in range(n // 2 + 1):
		ans.append(str(srt[i]))
		ans.append(str(srt[-(i + 1)]))
	ans.pop(-1)
	print(' '.join(ans))


def main():
	n = int(input())
	L = [int(x) for x in input().split()]
	result = solver(L)
	for x in result:
		print(x, end=' ')

def solver(L):
	L.sort()
	result = []
	for i in range(len(L) // 2):
		result.append(L[i])
		result.append(L[i + (len(L) + 1) // 2])
	if len(L) % 2 == 1:
		result.append(L[len(L) // 2])
	return result
main()


n = int(input())
a = sorted(map(int, input().split()))
l = 0
r = (n + 1) // 2
for i in range(n):
	if i % 2 == 0:
		print(a[l])
		l += 1
	else:
		print(a[r])
		r += 1


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())
arr = [int(i) for i in input().split()]
arr.sort()
res = [-1 for i in range(n)]
(left, right) = (0, n - 1)
for i in range(n):
	if (i + 1) % 2 == 1:
		res[i] = arr[left]
		left += 1
	if (i + 1) % 2 == 0:
		res[i] = arr[right]
		right -= 1
for r in res:
	print(r, end=' ')


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


n = int(input())
a = [int(i) for i in input().split()]
a.sort()
even_positions = a[(n + 1) // 2:]
odd_positions = a[:(n + 1) // 2]
l = []
for i in range(len(even_positions)):
	l.append(str(odd_positions[0]))
	l.append(str(even_positions[0]))
	odd_positions.pop(0)
	even_positions.pop(0)
if len(odd_positions) != 0:
	l.append(str(odd_positions[0]))
print(' '.join(l))


n = int(input())
a = list(map(int, input().split()))
a.sort()
E = []
Q = []
AA = []
for i in range(n):
	if i <= (n - 1) // 2:
		E.append(a[i])
	else:
		Q.append(a[i])
flag = True
for i in range(n):
	if flag:
		flag = False
		AA.append(E.pop(0))
	else:
		flag = True
		AA.append(Q.pop(-1))
print(*AA)


__author__ = 'Esfandiar'
n = int(input())
a = sorted(list(map(int, input().split())))
t = n - 1
for i in range(n // 2):
	print(a[i], end=' ')
	print(a[t], end=' ')
	t -= 1
if n % 2:
	print(a[n // 2], end=' ')


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
	elif s[k] <= s[k - 1]:
		pass
	else:
		print('Impossible')
		Po = 0
		break
if Po == 1:
	print(' '.join(map(str, s)))


import math
n = int(input())
l = list(map(int, input().split()))
l.sort()
a = math.ceil(n / 2)
b = l[a:]
c = l[:a]
ans = []
if len(b) == len(c):
	for i in range(n // 2):
		ans.append(c[i])
		ans.append(b[i])
else:
	for i in range(n // 2):
		ans.append(c[i])
		ans.append(b[i])
	ans.append(c[-1])
print(' '.join((str(i) for i in ans)))


n = int(input())
a = [int(x) for x in input().split(' ')]
a.sort()
for i in range(n):
	if i % 2 == 0:
		firval = a[i]
		secval = a[i - 1]
		if i == 0:
			continue
		elif firval > secval:
			(a[i], a[i - 1]) = (a[i - 1], a[i])
		elif secval >= firval:
			continue
	elif i % 2 != 0:
		firval = a[i]
		secval = a[i - 1]
		if firval < secval:
			(a[i], a[i - 1]) = (a[i - 1], a[i])
		elif secval <= firval:
			continue
final = []
for k in a:
	final.append(str(k))
print(' '.join(final))


import sys, math
sys.setrecursionlimit(10 ** 8)
n = int(input())
arr = list(map(int, input().split()))
arr.sort()
x = []
z = 1
for i in range(n // 2):
	x.append(arr[i])
	x.append(arr[len(arr) - i - 1])
if n % 2 == 1:
	x.append(arr[n // 2])
for i in range(n):
	if i % 2 == 1:
		if x[i] < x[i - 1]:
			print('Impossible')
			z = 0
			break
	elif x[i] > x[i - 1]:
		print('Impossible')
		z = 0
		break
if z != 0:
	print(' '.join(map(str, x)))


nb = int(input())
numbers = sorted([int(x) for x in input().split()])
for i in range(2, nb, 2):
	(numbers[i - 1], numbers[i]) = (numbers[i], numbers[i - 1])
print(*numbers)


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())
l = list(map(int, input().split()))
l.sort()
i = 0
j = n - 1
d = []
while i < j:
	d.append(l[i])
	d.append(l[j])
	i = i + 1
	j = j - 1
if n % 2 == 1:
	d.append(l[n // 2])
print(*d)


n = int(input())
ln = list(map(int, input().split()))
ln.sort()
ans = [0 for _ in range(n)]
i = 0
j = 0
while i < n:
	ans[i] = ln[j]
	j += 1
	i += 2
i = 1
while i < n:
	ans[i] = ln[j]
	j += 1
	i += 2
for e in ans:
	print(e, end=' ')
print('')


n = int(input())
a = sorted(map(int, input().split()))
a = [x for l in zip(a[:0 - -n // 2], a[0 - -n // 2:]) for x in l] + [a[n // 2]]
print(*a[:n])


def z_sort(n, seq):
	seq.sort()
	index = 0
	while index < n - 1:
		if index % 2 != 0:
			(seq[index], seq[index + 1]) = (seq[index + 1], seq[index])
		index += 1
	return list(map(str, seq))
n = int(input())
seq = list(map(int, input().split()))
zsorted = z_sort(n, seq)
print(' '.join(zsorted))


from functools import cmp_to_key
from collections import deque, Counter
from heapq import heappush, heappop
from math import log, ceil
import sys
import os
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
if sys.version_info[0] < 3:
	(sys.stdin, sys.stdout) = (FastIO(sys.stdin), FastIO(sys.stdout))
else:
	(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))

def print(*args, **kwargs):
	(sep, file) = (kwargs.pop('sep', ' '), kwargs.pop('file', sys.stdout))
	at_start = True
	for x in args:
		if not at_start:
			file.write(sep)
		file.write(str(x))
		at_start = False
	file.write(kwargs.pop('end', '\n'))
	if kwargs.pop('flush', False):
		file.flush()

def inp():
	return sys.stdin.readline().rstrip('\r\n')

def ii():
	return int(inp())

def si():
	return str(inp())

def li(lag=0):
	l = list(map(int, inp().split()))
	if lag != 0:
		for i in range(len(l)):
			l[i] += lag
	return l

def mi(lag=0):
	matrix = list()
	for i in range(n):
		matrix.append(li(lag))
	return matrix

def lsi():
	return list(map(str, inp().split()))

def print_list(lista, space=' '):
	print(space.join(map(str, lista)))

def bisect_left(a, x):
	left = 0
	right = len(a)
	while left < right:
		mid = (left + right) // 2
		if a[mid] < x:
			left = mid + 1
		else:
			right = mid
	return left

def bisect_right(a, x):
	left = 0
	right = len(a)
	while left < right:
		mid = (left + right) // 2
		if a[mid] > x:
			right = mid
		else:
			left = mid + 1
	return left

def bisect_elements(a, x):
	return bisect_right(a, x) - bisect_left(a, x)
MOD = 10 ** 9 + 7
maxN = 5
FACT = [0] * maxN
INV_FACT = [0] * maxN

def add(x, y):
	return (x + y) % MOD

def multiply(x, y):
	return x * y % MOD

def power(x, y):
	if y == 0:
		return 1
	elif y % 2:
		return multiply(x, power(x, y - 1))
	else:
		a = power(x, y // 2)
		return multiply(a, a)

def inverse(x):
	return power(x, MOD - 2)

def divide(x, y):
	return multiply(x, inverse(y))

def allFactorials():
	FACT[0] = 1
	for i in range(1, maxN):
		FACT[i] = multiply(i, FACT[i - 1])

def inverseFactorials():
	n = len(INV_FACT)
	INV_FACT[n - 1] = inverse(FACT[n - 1])
	for i in range(n - 2, -1, -1):
		INV_FACT[i] = multiply(INV_FACT[i + 1], i + 1)

def coeffBinom(n, k):
	if n < k:
		return 0
	return multiply(FACT[n], multiply(INV_FACT[k], INV_FACT[n - k]))

def create_graph(n, m, undirected=1, unweighted=1):
	graph = [[] for i in range(n)]
	if unweighted:
		for i in range(m):
			[x, y] = li(lag=-1)
			graph[x].append(y)
			if undirected:
				graph[y].append(x)
	else:
		for i in range(m):
			[x, y, w] = li(lag=-1)
			w += 1
			graph[x].append([y, w])
			if undirected:
				graph[y].append([x, w])
	return graph

def create_tree(n, unweighted=1):
	children = [[] for i in range(n)]
	if unweighted:
		for i in range(n - 1):
			[x, y] = li(lag=-1)
			children[x].append(y)
			children[y].append(x)
	else:
		for i in range(n - 1):
			[x, y, w] = li(lag=-1)
			w += 1
			children[x].append([y, w])
			children[y].append([x, w])
	return children

def dist(tree, n, A, B=-1):
	s = [[A, 0]]
	(massimo, massimo_nodo) = (0, 0)
	distanza = -1
	v = [-1] * n
	while s:
		(el, dis) = s.pop()
		if dis > massimo:
			massimo = dis
			massimo_nodo = el
		if el == B:
			distanza = dis
		for child in tree[el]:
			if v[child] == -1:
				v[child] = 1
				s.append([child, dis + 1])
	return (massimo, massimo_nodo, distanza)

def diameter(tree):
	(_, foglia, _) = dist(tree, n, 0)
	(diam, _, _) = dist(tree, n, foglia)
	return diam

def dfs(graph, n, A):
	v = [-1] * n
	s = [[A, 0]]
	v[A] = 0
	while s:
		(el, dis) = s.pop()
		for child in graph[el]:
			if v[child] == -1:
				v[child] = dis + 1
				s.append([child, dis + 1])
	return v

def bfs(graph, n, A):
	v = [-1] * n
	s = deque()
	s.append([A, 0])
	v[A] = 0
	while s:
		(el, dis) = s.popleft()
		for child in graph[el]:
			if v[child] == -1:
				v[child] = dis + 1
				s.append([child, dis + 1])
	return v

def parents_children_root_unrooted_tree(tree, n, root=0):
	q = deque()
	visited = [0] * n
	parent = [-1] * n
	children = [[] for i in range(n)]
	q.append(root)
	while q:
		all_done = 1
		visited[q[0]] = 1
		for child in tree[q[0]]:
			if not visited[child]:
				all_done = 0
				q.appendleft(child)
		if all_done:
			for child in tree[q[0]]:
				if parent[child] == -1:
					parent[q[0]] = child
					children[child].append(q[0])
			q.popleft()
	return (parent, children)

def all_longest_path_passing_from_node(parent, children, n):
	q = deque()
	visited = [len(children[i]) for i in range(n)]
	downwards = [[0, 0] for i in range(n)]
	upward = [1] * n
	longest_path = [1] * n
	for i in range(n):
		if not visited[i]:
			q.append(i)
			downwards[i] = [1, 0]
	while q:
		node = q.popleft()
		if parent[node] != -1:
			visited[parent[node]] -= 1
			if not visited[parent[node]]:
				q.append(parent[node])
		else:
			root = node
		for child in children[node]:
			downwards[node] = sorted([downwards[node][0], downwards[node][1], downwards[child][0] + 1], reverse=True)[0:2]
	s = [node]
	while s:
		node = s.pop()
		if parent[node] != -1:
			if downwards[parent[node]][0] == downwards[node][0] + 1:
				upward[node] = 1 + max(upward[parent[node]], downwards[parent[node]][1])
			else:
				upward[node] = 1 + max(upward[parent[node]], downwards[parent[node]][0])
		longest_path[node] = downwards[node][0] + downwards[node][1] + upward[node] - min([downwards[node][0], downwards[node][1], upward[node]]) - 1
		for child in children[node]:
			s.append(child)
	return longest_path
n = ii()
a = li()
res = [-1 for i in range(n)]
a.sort(reverse=True)
idx = 1
pos = 0
while idx < n:
	res[idx] = a[pos]
	pos += 1
	idx += 2
idx = 0
while idx < n:
	res[idx] = a[pos]
	pos += 1
	idx += 2
print_list(res)


n = int(input())
A = list(map(int, input().split()))
A.sort()
ans = []
for i in range(n):
	rez = i // 2
	if i % 2 == 0:
		z = A[rez]
	else:
		z = A[n - 1 - rez]
	ans.append(z)
print(' '.join(map(str, ans)))


n = int(input())
a = list(map(int, input().split()))
ans = []
check = sorted(a)
(i, j) = (0, n - 1)
while i < j:
	ans.append(check[i])
	ans.append(check[j])
	i += 1
	j -= 1
if i == j:
	ans.append(check[i])
print(*ans)


length = int(input())
input1 = list(map(int, input().split(' ')))
input1.sort(reverse=True)
i = 0
j = 1
answer = [0] * length
while j < length:
	answer[j] = input1[i]
	i += 1
	j += 2
j = 0
while j < length:
	answer[j] = input1[i]
	i += 1
	j += 2
for i in range(0, len(answer)):
	print(answer[i], end=' ')


n = int(input())
x = sorted(list(map(int, input().split())))
a = []
for i in range(n // 2):
	a.append(x[i])
	a.append(x[-i - 1])
if n % 2 != 0:
	a.append(x[n // 2])
for j in range(1, n):
	if j % 2 != 0:
		if a[j] < a[j - 1]:
			print('Impossible')
			exit()
	elif a[j] > a[j - 1]:
		print('Impossible')
		exit()
print(*a)


def main():
	n = int(input())
	a = sorted(map(int, input().split()))
	result = [0] * n
	result[::2] = a[:(n + 1) // 2]
	result[1::2] = a[(n + 1) // 2:]
	print(*result)
main()


n = int(input())
a = list(map(int, input().split()))
a.sort()
l = []
for i in range(n // 2):
	if a[i] <= a[n - 1 - i]:
		l.append(a[i])
		l.append(a[n - 1 - i])
	else:
		print('impossible')
		exit()
if n % 2 != 0:
	l.append(a[n // 2])
print(*l)


n = int(input())
arr = [int(x) for x in input().split(' ')]
sorted_arr = sorted(arr, reverse=True)
z_sorted_arr = []
j = n - 1
for i in range(0, int(n / 2)):
	z_sorted_arr.append(sorted_arr[j])
	z_sorted_arr.append(sorted_arr[i])
	j = j - 1
if n % 2 != 0:
	z_sorted_arr.append(sorted_arr[int(n / 2)])
print(' '.join([str(x) for x in z_sorted_arr]))


n = int(input())
a = list(map(int, input().split()))
a.sort()
p = n // 2 if n % 2 == 0 else n // 2 + 1
t = [0] * n
j = 0
for i in range(n):
	if i % 2 == 0:
		t[i] = a[j]
		j += 1
	else:
		t[i] = a[p]
		p += 1
pos = True
for i in range(n):
	if i % 2 == 1:
		if t[i] < t[i - 1]:
			pos = False
			break
		if i + 1 < n and t[i] < t[i + 1]:
			pos = False
			break
if not pos:
	print('impossible')
else:
	print(' '.join([str(i) for i in t]))


n = int(input())
x = input()
x = x.split()
for i in range(n):
	x[i] = int(x[i])
a1 = list()
a2 = list()
x = sorted(x)
for i in range(int(n / 2)):
	a1.append(x[i])
for i in range(int(n / 2), n):
	a2.append(x[i])
a1.sort()
a2.sort()
a2 = a2[::-1]
res = list()
for i in range(len(a2)):
	if i < len(a1):
		res.append(a1[i])
	res.append(a2[i])
f = ''
for i in range(n):
	f += str(res[i]) + ' '
print(f)


from sys import stdin
n = int(stdin.readline().strip())
nums = sorted([int(i) for i in stdin.readline().strip().split()])
a = []
if n % 2 == 0:
	for i in range(0, int(n / 2)):
		a.append(str(nums[i]))
		a.append(str(nums[n - 1 - i]))
else:
	for i in range(0, int((n - 1) / 2)):
		a.append(str(nums[i]))
		a.append(str(nums[n - 1 - i]))
	a.append(str(nums[int((n - 1) / 2)]))
print(' '.join(a))


def swap(a: list, aux, i, j):
	a[j] = a[i]
	a[i] = aux

def z_sort(n: int, a: list):
	a = sorted(a)
	j = 1
	for i in range(2, n, 2):
		if a[i] > a[i - 1]:
			swap(a, a[j], i, j)
			j += 2
	for i in range(n - 1):
		print(a[i], end=' ')
	print(a[n - 1])

def main():
	n = int(input())
	a = list(map(int, input().split()))
	z_sort(n, a)
main()


import math
n = int(input())
mid = math.ceil(n / 2)
a = [int(x) for x in input().split()]
a.sort()
b = [None] * n
for i in range(n):
	b[(i >= mid) + 2 * (i - mid) if i >= mid else 2 * i] = a[i]
s = ''
for x in b:
	s += str(x) + ' '
print(s)


n = int(input())
a = list(map(int, input().strip().split()))
a.sort()
res = [0] * n
i = 0
while 2 * i < n:
	res[2 * i] = a[i]
	i += 1
j = 0
while 2 * j + 1 < n:
	res[2 * j + 1] = a[i]
	i += 1
	j += 1
print(' '.join(map(str, res)))


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


import math
n = int(input())
list = list(map(int, input().split()))
list.sort()
small = list[:int(math.ceil(n / 2))]
big = list[int(math.ceil(n / 2)):]
iter = 0
for i in range(n):
	if i % 2 == 0:
		list[i] = small[iter]
	else:
		list[i] = big[iter]
		iter += 1
flag = True
for i in range(n):
	if i % 2 == 0 and (i > 0 and list[i] > list[i - 1] or (i < n - 1 and list[i] > list[i + 1])):
		flag = False
		break
if flag:
	print(' '.join(map(str, list)))
else:
	print(-1)


import sys
input = sys.stdin.readline

def inp():
	return int(input())

def inlt():
	return list(map(int, input().split()))

def insr():
	s = input()
	return list(s[:len(s) - 1])

def invr():
	return map(int, input().split())

def main():
	n = inp()
	arr = inlt()
	arr.sort()
	new_arr = []
	index = 0
	forward = False
	while len(new_arr) < n:
		if forward == False:
			new_arr.append(arr[index])
			forward = True
		else:
			forward = False
			new_arr.append(arr[-(index + 1)])
			index += 1
	print(' '.join(map(str, new_arr)))
main()


import sys

def getSrcData():
	f = sys.stdin
	buf = f.read()
	buf = buf.split('\n')
	cnt = int(buf[0])
	if cnt != 0:
		src = buf[1].split(' ')
		src = [int(i) for i in src]
	else:
		src = []
	return (cnt, src)

def getTransform(cnt, src):
	src.sort()
	result = []
	for i in range(0, cnt // 2):
		result.append(src[i])
		result.append(src[cnt - 1 - i])
	if cnt % 2 == 1:
		result.append(src[cnt // 2])
	return result

def saveResult(result):
	if len(result) == 0:
		pbuf = 'Impossible'
	else:
		pbuf = [str(i) for i in result]
		pbuf = ' '.join(pbuf)
	f = sys.stdout
	f.write(pbuf)
	f.flush()

def run():
	(cnt, src) = getSrcData()
	if cnt != 0:
		result = getTransform(cnt, src)
	else:
		result = []
	saveResult(result)
run()