No tag edit access

A. Difference Row

time limit per test

2 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputYou 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}.

Codeforces (c) Copyright 2010-2017 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Oct/17/2017 14:21:55 (p1).

Desktop version, switch to mobile version.

User lists

Name |
---|