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
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 |
---|