Love Evenness

View as PDF

Submit solution

Points: 5
Time limit: 2.0s
Memory limit: 256M
Python 512M

Problem type

After watching Online Art Sword yesterday, you and your best friend Donny have been summoned to the realm of an evil necromancer as heroes! The residents of this world ask you to help them defeat the demon king before it conquers the rest of the holy land. Being the hero that you are, you agree to help them. However, as the evil, sadistic necromancer loves painful games, you can only defeat the demon king by beating it at a game:

There is an array of M integers, M being even, arranged into a tower. The M integers each have an index, index 1 being the integer on the bottom. The next M-1 integers each have an index 1 higher than the integer under it.

On each one of the demon king's moves, the demon king picks an integer from an even index and adds it to its collection. For each of your moves, you pick an integer from an odd index and add it to your collection. When a number has been picked, that integer is removed along with its index, and all the integers above have their indices decreased by 1.

The demon king always starts first and the two players alternate turns, playing until there are no more integers left. The score of a player is calculated by summing together the integers in that player's collection once the game ends.

Given an array of 2N integers a, with the i^{th} integer denoted as a_i: If you can reorder array a before the game starts and both you and the demon king play the game with array a optimally, what is the maximum possible difference between your score and the score of the demon king?


1 \le N \le 10^6

1 \le a_i \le 10^3

Input Specification

The first line contains the integer N.

The next line contains the 2N integers, space-separated, from a.

Output Specification

Output one integer, the maximum possible difference between your score and the score of the demon king.

Sample Input

7 6 6 6

Sample Output



You can end up with the integers 6 7, leaving 6 6 for the demon king.


There are no comments at the moment.