You want to arrange n integers a_1, a_2, ..., a_{n} in some order in a row. Let's define the value of an arrangement as the sum of differences between all pairs of adjacent integers.

More formally, let's denote some arrangement as a sequence of integers x_1, x_2, ..., x_{n}, where sequence x is a permutation of sequence a. The value of such an arrangement is (x_1 - x_2) + (x_2 - x_3) + ... + (x_{n} - 1 - x_{n}).

Find the largest possible value of an arrangement. Then, output the lexicographically smallest sequence x that corresponds to an arrangement of the largest possible value.


-----Input-----

The first line of the input contains integer n (2 ≤ n ≤ 100). The second line contains n space-separated integers a_1, a_2, ..., a_{n} (|a_{i}| ≤ 1000).


-----Output-----

Print the required sequence x_1, x_2, ..., x_{n}. Sequence x should be the lexicographically smallest permutation of a that corresponds to an arrangement of the largest possible value.


-----Examples-----
Input
5
100 -100 50 0 -50

Output
100 -50 0 50 -100 



-----Note-----

In the sample test case, the value of the output arrangement is (100 - ( - 50)) + (( - 50) - 0) + (0 - 50) + (50 - ( - 100)) = 200. No other arrangement has a larger value, and among all arrangements with the value of 200, the output arrangement is the lexicographically smallest one.

Sequence x_1, x_2, ... , x_{p} is lexicographically smaller than sequence y_1, y_2, ... , y_{p} if there exists an integer r (0 ≤ r < p) such that x_1 = y_1, x_2 = y_2, ... , x_{r} = y_{r} and x_{r} + 1 < y_{r} + 1.

Difficulty: interview

Starter code:

Solutions:
n = int(input())
A = list(map(int, input().split()))
A.sort()
A[0], A[-1] = A[-1], A[0]
print(" ".join(list(map(str, A))))

n=int(input())

A=list(map(int,input().split()))

A.sort()

print(A[-1],end=" ")
for i in range(1,n-1):
    print(A[i],end=" ")
print(A[0])


n = int(input())
a = list(map(int, input().split()))
mi = min(a)
ma = max(a)
ans = []
ans.append(ma)
a.sort()
print(ma, *a[1:len(a) - 1], end = ' ')
print(mi)

n = int(input())
A = list(map(int, input().split()))
x = max(A)
A.pop(A.index(max(A)))
y = min(A)
A.sort()
A.pop(A.index(min(A)))
print(' '.join(list(map(str, [x] + A + [y]))))


n, seq = int(input()), list(map(int, input().split()))
a0, an = seq.pop(seq.index(max(seq))), seq.pop(seq.index(min(seq)))
print(' '.join(map(str, [a0] + sorted(seq) + [an])))


a = int(input())
arr = list(map(int, input().split()))
if(a == 2):
    print(*(sorted(arr)[::-1]))
else:
    arr = sorted(arr)[::-1]
    arr[1:-1] = sorted(arr[1:-1])
    print(*arr)

n = int(input())
A = list(map(int, input().split()))
Max = max(A)
Min = min(A)
ind1 = A.index(Max)
A.pop(ind1)
ind2 = A.index(Min)
A.pop(ind2)
if len(A) > 0:
    print(str(Max), ' '.join(map(str, sorted(A))), str(Min))
else:
    print(str(Max), str(Min))

n = int(input())
A = sorted(list(map(int, input().split())))
print(A[-1], ' '.join(map(str, A[1:-1])), A[0])


import sys
input = sys.stdin

line = input.readline()
n = int(line)
line = input.readline()
d = list(map(int, line.split(" ")))
maxn = maxc = max(d)
minn = minc = min(d)

ans = []
for num in d:
  if num == maxc:
    maxc = None
  elif num == minc:
    minc = None
  else:
    ans.append(num)

ans.sort()
print(maxn, end=" ")
for num in ans:
  print(num, end=" ")
print(minn)


n = int(input())
a = list(map(int, input().split()))
a.sort()
a[0],a[-1] = a[-1],a[0]
print(*a)


n = int(input()) 
data = sorted(list(map(int, input().split())))
print(data[-1], end = ' ')
print(*data[1:-1], end = ' ')
print(data[0])


n = int(input())
list1 = list(map(int, input().split()))
print(max(list1), " ".join(map(str, sorted(list1)[1:-1])), min(list1))


N = int(input())
A = sorted(list(map(int, input().split())))
A[0], A[-1] = A[-1], A[0]
for x in A : print(x, end=" ")


n = int(input())
a = list(map(int, input().split()))
a.sort()
s = a[0]
a = a[1:]
print(a[n-2], *a[:n-2], end=' ')
print(s)

def __starting_point():
    inp = input()
    inp = input()
    arr = inp.split(" ")
##    print(len(arr))
    Li = []
    Ls = []
    for a in arr:
        Li.append(int(a))

    Li.sort()
    fst = Li.pop(0)
    lst = Li.pop(-1)
    ans = str(lst)
    for x in Li:
        Ls.append(str(x))
##    Ls.sort()
##    print(len(Ls))
    for s in Ls:
        ans+=" "+s
    ans+=" "+str(fst)
    print(ans)
    
        
        

__starting_point()

n = int(input())
seq = sorted(list(map(int, input().split())))

print(' '.join(map(str, [seq[-1]] + seq[1:-1] + [seq[0]])))

input()
a = sorted(input().split(), key=int)
print(a[-1], ' '.join(a[1:-1]), a[0])


3

n = int(input())
lst = sorted(map(int, input().split()))
lst[1:-1] = lst[-2:0:-1]
print(*tuple(reversed(lst)))


while(1):
    try:
        n=int(input())
        a=list(map(int,input().split()))
        a.sort()
        print(a[n-1],end=" ")
        for i in range(1,n-1):
            print(a[i],end=" ")
        print(a[0])
    except EOFError:
        break
        

n = int (input ())
a = list (map (int, input().split()))
a.sort ()
a[0],a[-1] = a[-1],a[0]
for i in a:
  print (i,end=' ')


n = int(input())
a = list(map(int, input().split()))
a.sort()
a[0], a[-1] = a[-1], a[0]
print(*a)

N=int(input())
num=[]
i=0
IN=input().split()
while(i<N):
		num.append(int(IN[i]))
		i=i+1
num.sort()
num[0],num[len(num)-1]=num[len(num)-1],num[0]
for i in num:
	print(i,end=' ')
		

input()
a = sorted(map(int, input().split()))
t = a[-1]
a[-1] = a[0]
a[0] = t
print(*a)

n = int(input())
arr = list(int(x) for x in input().split(' '))
mi = min(arr)
ma = max(arr)
arr.remove(mi)
arr.remove(ma)
arr.sort()
print(' '.join(map(str,[ma] + arr + [mi])))