B. The Three-Body Problem
Description
In the three-body world, humans in the Earth
are attacked by dual-vector foil, which reduces
the human’s three-dimensional space into a
two-dimensional space. Only Cheng Xin and
few other people have survived. Suppose
Cheng Xin invents a technique, which can bring
humans back into life (but cannot convert the
2D world into 3D), many years later, and long
before the Zeroer decides to reboot the
Universe. Now cities are like lines. People living in one city move on a line, and they have their
own private houses.
One day, people in HK (in the 2D world) plan to build an office building, and staffs working
here need to travel between the office and their own houses. We use 1, 2, …, n to denote each
person, whose house location is xi. The travelling cost of one-unit length is one for all staffs. For
instance, if the staff i is located at xi =1 and the office building is at y=5, the cost for him to go to
work is |1-5|=4. As the natural resources are extremely scarce then, people have to find a
position to build the office such that the total energy consumption, Given the locations of staffs, could you help find the best location to build the office
and calculate the minimum total travelling cost of all staffs? For simplicity, you only need to tell
them the minimum total cost.
Input
The input contains several cases and is terminated by end of line. Each test case contains two
lines, the first line contains one integer n (1≤n≤5000), the number of people. The second line
contains n integers xi (1≤xi≤2
31
-1), indicating the location of staff i. Since you have not learned
sorting algorithms, the given locations are in either descending or ascending order.
Output
For each test case, print the minimum total cost of all agents.
Example