Problem G
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. Hunters may choose to use or not use a portal as they wish.
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.
Input
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)$.
Output
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 |
2 |