347A.md (1930B)
1 Source: https://codeforces.com/problemset/problem/347/A 2 3 A. Difference Row 4 5 time limit per test 6 7 2 seconds 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 stdin 16 17 output 18 19 stdout 20 21 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. 22 23 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*). 24 25 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. 26 27 Input 28 29 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). 30 31 Output 32 33 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. 34 35 Examples 36 37 Input 38 39 ``` 40 5 41 100 -100 50 0 -50 42 ``` 43 44 Output 45 46 ``` 47 100 -50 0 50 -100 48 ``` 49 50 Note 51 52 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. 53 54 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.