URI Online Judge | 2567

Virus

By Flávio Zavan, UFPR BR Brazil

Timelimit: 1

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.

Input

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

Output

For each test case, print a single line with the maximum lethality level that the infection can take.

Input Sample Output Sample

4
4 9 43 10
3
0 100 50

40
100