+ Time Limit: 2 seconds + Memory Limit: 256 megabytes ------------ Nelly has $n$ crystal jars, each of which has a certain **transparency**. She wants to place all the jars in a row, one after another. The transparency of jar $i$ is $a_i$. However, for some reasons, placing jars next to each other causes some of them to crack! The amount of cracking of each jar depends on the jars placed before and after it. Note that cracking a jar does not change its transparency. Suppose that in a certain ordering, jar $i$ is placed at some position. To determine the amount of cracking of this jar, among all jars that are **before it**, consider the most transparent jar as $j$, and similarly, among all jars that are **after it**, consider the most transparent jar as $k$. Then the amount of cracking of jar $i$ is determined as follows: + If $a_i < min(a_j, a_k) \ $, jar $i$ cracks by an amount of $min(a_j, a_k) - a_i \ $. + If $a_i > min(a_j, a_k) \ $ and $a_i < max(a_j, a_k) \ $, jar $i$ cracks by an amount of $max(a_j, a_k) - a_i \ $. + If $a_i > max(a_j, a_k) \ $, jar $i$ does not crack, and its amount of cracking is equal to zero. For the first jar, we only consider the jars after it, and for the last jar, we only consider the jars before it. Also, if there are no jars on one side, we consider the maximum transparency on that side to be $0$. We define the fragility of an ordering as the sum of the amounts of cracking of all $n$ jars. Nelly gives her jars to Amirhosein and asks him to find the minimum possible fragility among all permutations of these $n$ jars. Amirhosein is a little busy, so he asks you to help him find the answer. # Input The first line contains an integer $n$, the number of crystal jars. $$1 \leq n \leq 3*10^5$$ The second line contains $n$ integers, where the $i$-th integer represents the transparency of jar $i$. $$1 \leq a_i \leq 10^9$$ It is guaranteed that no two jars have the same transparency. # Output Print the minimum possible fragility among all permutations of the $n$ jars in a single line. # Examples ## Sample input 1 ``` 5 3 1 4 2 5 ``` ## Sample output 1 ``` 6 ``` ## Sample input 2 ``` 7 7 1 10 2 6 8 12 ``` ## Sample output 2 ``` 20 ```