# Elephant Coach

*Limits: 2 sec., 256 MiB*

While enjoying beautiful and in-sync elephant dancing in Thailand, Andrii decided that he is going to become an elephant coach. "Once I return to Ukraine, I’ll be the best elephant coach in the world" he proclaimed.

Unfortunately, there are no elephants where Andrii lives, only street cats. But Andrii is OK working with cats too.

Let’s consider a street as a line, and cats as points on the line. There is a total of \(n\) cats on the street, and the \(i\)-th cat is located at point \(x_i\). In order to start coaching Andrii has to bring all cats to the same point. In a single minute, Andrii can select any set of cats and order all of them to either move left or right by a single coordinate point (all cats move in the same direction).

Help Andrii find the minimum number of minutes that he needs to spend to get all cats to the same point.

# Input

The first line contains a single positive integer \(n\) – the number of cats on the street where Andrii lives.

The next line contains \(n\) space-separated integers \(x_i\) – the initial coordinates of the cats.

# Output

In a single line print a single integer – the minimum number of minutes needed.

# Constraints

\(1 \le n \le 10^5\),

\(0 \le x_i \le 10^9\).

# Samples

Input (stdin) | Output (stdout) |
---|---|

2 4 7 | 3 |

Input (stdin) | Output (stdout) |
---|---|

7 3 1 1 2 10 7 4 | 9 |

# Notes

In the first sample the first cat moves three time to the right.

In the second sample the movies can go like this:

cats 2, 3 move to the right

cats 2, 3, 4 move to the right

cats 1, 2, 3, 4 move to the right

cat 5 moves to the left

**3 times**cats 5, 6 move to the left

**3 times**

**Source:**DE:CODED 2016### Submit a solution

Element Type | Created | Who | Problem | Compiler | Result | Time (sec.) | Memory (MiB) | # | Actions |
---|

Element Type | Created | Who | Problem | Compiler | Result | Time (sec.) | Memory (MiB) | # | Actions |
---|