By Flávio Zavan, UFPR Brazil
The Department of Public Health of Nlogonia has just issued an alert. A virus is infecting the entire population.
After a lot of studies, the Nlogonia’s researchers found out that after infiltrating a host body, the viruses match in pairs to become lethal. The level of lethality of an infection is determined by the sum of the age difference in days of the paired viruses. Virues not paired don’t influence the level.
Thus, if there are 4 viruses in the host body with ages (in days), equals to:
4, 10, 9, 43
And they are paired as follows:
4 with 9, 43 with 10
Then the level of lethality would be (9 - 4) + (43 - 10) = 38.
The Department of Public Health of Nlognia asked you to write a program that, given the virus count in a host and the age of each of them, calculate the maximum level of lethality that the infection can take.
The input contains several test cases. The first line of each test case consists of an integer N (1 ≤ N ≤ 1000), the number of viruses in the host body. The following line contains N integers ai (0 ≤ ai ≤ 1000) separated by blank spaces, the ages (in days) of all the viruses in the host body.
The input ends with end-of-file (EOF).
For each test case, print a single line with the maximum lethality level that the infection can take.
Input Sample | Output Sample |
4 |
40 |