The Minima Game

Alice and Bob are playing the minima game. A set of cards is placed on the table, each inscribed with a positive integer. The players take turns – with Alice starting first – and on each turn a player picks an arbitrary positive number of cards from the table. For that move the player receives points equal to the minimum value among the chosen cards. The game ends when all cards have been removed from the table. Both players aim to maximize the difference between their own total score and their opponent’s score.

Your task is to determine the outcome of the game (i.e. Alice’s score minus Bob’s score) assuming both players play optimally.

Note: Since the optimal strategy requires considering all possible moves, the number of cards is guaranteed to be small (n ≤ 15).

inputFormat

The first line contains an integer n (1 ≤ n ≤ 15), the number of cards. The second line contains n space‐separated positive integers, where each integer represents the number inscribed on a card.

outputFormat

Output a single integer – the maximum possible difference (Alice’s score minus Bob’s score) when both players play optimally.

sample

1
5

5