跳到主要内容
图灵 OJTURING / ONLINE JUDGE

#F2317. Difference Row

    ID: 2323 传统题 2000ms 256MiB 尝试: 0 已通过: 0 难度: 3 上传者: 标签>构造模拟排序算法思想编程与模拟基础难度共享题库Codeforces英文题面题目来源题面语言

Difference Row

题目描述

A. Difference Row
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You want to arrange n integers a1,a2,...,an 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 x1,x2,...,xn, where sequence x is a permutation of sequence a. The value of such an arrangement is (x1-x2)+(x2-x3)+...+(xn-1-xn).

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 a1, a2, ..., an (|ai|≤1000).

Output

Print the required sequence x1,x2,...,xn. 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 x1,x2,... ,xp is lexicographically smaller than sequence y1,y2,... ,yp if there exists an integer r (0≤r<p) such that x1=y1,x2=y2,... ,xr=yr and xr+1<yr+1.

题目来源：fps-www.educg.net-codeforce-1-2833.xml.zip；FPS 共享题包，题包内第 1933 题。保留原作者与原赛事署名。