ICPC Vietnam National Programming Contest 2019

Start

2019-11-02 17:00 AKDT

ICPC Vietnam National Programming Contest 2019

End

2019-11-02 22:00 AKDT
The end is near!
Contest is over.
Not yet started.
Contest is starting in -249 days 13:59:03

Time elapsed

5:00:00

Time remaining

0:00:00

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