On Christmas morning, Ashley and Oleg woke up to find ~N~ presents under their tree. The presents were unlabelled, so their parents told them to split up the presents amongst themselves.

Ashley and Oleg decided on the following scheme to split up the presents: starting with Ashley, they will take turns taking a present for themselves. Each present has a value and, in order to not appear greedy, neither person will take a present with a greater value than the present the other person just took. For her first present, Ashley can choose any present.

Suppose ~A~ is the sum of the present values that Ashley took, and ~B~ is the sum that Oleg took. Ashley would like to maximize ~A - B~, while Oleg would like to maximize ~B - A~. If both people choose their presents optimally, what would be the value of ~A - B~?

Input Specification

The input begins with an integer ~N~ ~(1 \leq N \leq 500\ 000)~. The next line contains ~N~ values ~A_i~ ~(1 \leq A_i \leq 10^9)~, the values of the presents.

For 30% of the cases, ~N \le 20~.
For 60% of the cases, ~N \le 1000~.

Output Specification

Output the value of ~A - B~ if both Ashley and Oleg choose their presents optimally.

Sample Input 1

4
1 3 8 7

Sample Output 1

5

Explanation of Sample Input

Ashley should take the present with value ~7~ first. Then Oleg would not take the present with value ~8~ to not look greedy, so he would take the present of value ~3~. Then Ashley would take the final present with value ~1~.