## Love Evenness

View as PDF

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

Author:
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 integers, being even, arranged into a tower. The integers each have an index, index being the integer on the bottom. The next integers each have an index 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 .

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 integers , with the integer denoted as : If you can reorder array before the game starts and both you and the demon king play the game with array optimally, what is the maximum possible difference between your score and the score of the demon king?

#### Input Specification

The first line contains the integer .

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

#### Output Specification

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

#### Sample Input

2
7 6 6 6

#### Sample Output

1

#### Explanation

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