Gathering in Yorknew
Hunters from all over the world are gathering in Yorknew — where the ‘International Hunter Programming Contest $2020$’ will take place. As Gon has previously passed the final round of Hunter Exam and became a Hunter, you may be able to see Gon in Yorknew!
There is exactly one road leading to Yorknew — an infinitely long and narrow road. For simplicity, you can imagine the road as a straight line.
$h$ Hunters are going to Yorknew city. The $i$-th Hunter is currently at location $x_ i$. Yorknew city is at location $0$. The Hunters all walk very fast — they move with velocity of $1$ unit per second.
To avoid traffic jam, Yorknew city administrators have decided to build two portals. It takes exactly $0$ second to teleport from one portal to the other.
The administrators want to place the two portals at some integer positions on the road, such that the total time it takes for all $h$ Hunter to reach Yorknew city is as small as possible.
The first line of the input contains exactly one integer $h$ — the number of Hunters $(1 \le h \le 10^5)$.
The second line contains exactly $h$ integers: the $i$-th number, $x_ i$ is the current location of the $i$-th Hunter. $(-10^9 \le x_ i \le 10^9)$.
Print only one integer — the total time it takes for all Hunters to reach Yorknew city.
Explanation of sample test
There are $3$ Hunters, at locations $4$, $5$ and $6$. An optimal plan is to place two portals at $0$ and $5$.
The time it takes for the $3$ Hunters to reach Yorknew city are: $1$, $0$ and $1$. Thus, the total time is $1 + 0 + 1 = 2$.
|Sample Input 1||Sample Output 1|
3 4 5 6