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
def main():
	n = int(input())
	a = sorted(map(int, input().split()))
	result = [0]*n
	# print(result)
	# basic = 0
	# # a.sort()
	# # print(a)
	# count = 0 
	# if n&1==0:
	# 	while basic<n:
	# 		# print(basic, count)
	# 		result[count] = a[basic]
	# 		if count==n-2:
	# 			count = 1
	# 			basic+=1
	# 			# print(basic, count)
	# 			result[count]  = a[basic]
	# 		basic+=1
	# 		count+=2
	# else:
	# 	while basic<n:
	# 		# print(basic, count)
	# 		result[count] = a[basic]
	# 		if count==n-1:
	# 			count = 1
	# 			basic+=1
	# 			# print(basic, count)
	# 			result[count]  = a[basic]
	# 		basic+=1
	# 		count+=2

	result[::2] = a[:(n+1)//2]
	result[1::2] = a[(n+1)//2:]
	# print(a[basic])
	print(*result)
	
main()