The Minima Game

Alice and Bob recently learned a game they came to love, the minima game. The rules are as follows.

Several cards lie on a table, each showing a single positive integer. The players move alternately, and Alice moves first. On a move, a player takes any positive number of cards from the table (one or more). For that move the player earns points equal to the smallest number among the cards just taken. The game ends when the last card is removed from the table.

Each player wants to maximize the difference between their own total score and their opponent's total score.

This game has an optimal strategy. For a given set of cards, determine the result of the game when both players play optimally.

The first line contains one integer $n$ ($1 \le n \le 10^6$), the number of cards.

The second line contains the $n$ positive integers $k_1, k_2, \dots, k_n$ ($1 \le k_i \le 10^9$) written on the cards, separated by single spaces.

Print a single integer: the number of points by which Alice beats Bob when both play optimally. If Bob ends up with more points, the value should be negative.

In the sample, Alice takes the single card showing $3$ and earns three points. Bob then takes both remaining cards and earns one point (the smaller of the two values). The game ends three to one, so Alice wins by two points.