Switchback
Medium
Execution time limit is 0.2 seconds
Runtime memory usage limit is 64 megabytes
Visitors are drawn to attractions like "Roller Coasters" primarily because of the thrilling height differences. The park has acquired N modules, each with a specific height ( M_i ), which can be assembled into a single attraction. Your task is to arrange these modules in such a way that the total height difference, calculated as:
[ P = |M_1 - M_2| + |M_2 - M_3| + \ldots + |M_{N-1} - M_N| ]
is maximized.
Input
The input begins with a line containing the number of modules N ((4 \leq N \leq 100)). The next line contains N natural numbers representing the heights of the modules ( M_1, M_2, \ldots, M_N ) ((1 \leq M_i \leq 1000)). These numbers are separated by spaces.
Output
Output the maximum possible total height difference P.
Examples
Input #7
Answer #7
Submissions 570
Acceptance rate 5%