B - カード取りゲーム 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 300 点

問題文

高橋君と青木君はカード取りゲームで対戦しています。

テーブルの上には N 枚のカードが並べられています。各カードには 1 から N までの番号が付けられており、カード i には正の整数 A_i が書かれています。

ゲームは以下のルールで進行します：

  1. 両者の得点は最初 0 点です。
  2. 高橋君が先手で、高橋君と青木君は交互にターンを行います。
  3. 自分のターンでは、テーブルに残っているカードの中からちょうど 1 枚を選んで取らなければなりません（パスはできません）。取ったカードはテーブルから除かれ、そのカードに書かれた整数がそのプレイヤーの得点に加算されます。
  4. すべてのカードが取られたらゲーム終了です。

以上のルールにより、高橋君は \lceil N/2 \rceil 枚、青木君は \lfloor N/2 \rfloor 枚のカードを取ることになります。

高橋君は（高橋君の得点）-（青木君の得点）を最大化するように、青木君は（高橋君の得点）-（青木君の得点）を最小化するように、それぞれ最適にプレイします。両者が最適にプレイしたときの（高橋君の得点）-（青木君の得点）を求めてください。

制約

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq A_i \leq 10^9
  • 入力はすべて整数

入力

N
A_1 A_2 \ldots A_N
  • 1 行目には、カードの枚数を表す整数 N が与えられる。
  • 2 行目には、カード i (i = 1, 2, \ldots, N) に書かれた整数 A_i が N 個、スペース区切りで与えられる。

出力

両者が最適にプレイしたときの（高橋君の得点）-（青木君の得点）を整数として 1 行で出力せよ。

入力例 1

3
10 20 30

出力例 1

20

入力例 2

5
1 2 3 4 5

出力例 2

3

入力例 3

8
100 50 80 120 90 30 70 60

出力例 3

60

Score : 300 pts

Problem Statement

Takahashi and Aoki are playing a card taking game against each other.

There are N cards laid out on the table. Each card is numbered from 1 to N, and card i has a positive integer A_i written on it.

The game proceeds according to the following rules:

  1. Both players start with a score of 0.
  2. Takahashi goes first, and Takahashi and Aoki take turns alternately.
  3. On their turn, a player must choose exactly 1 card from the cards remaining on the table and take it (passing is not allowed). The taken card is removed from the table, and the integer written on that card is added to that player's score.
  4. The game ends when all cards have been taken.

According to the above rules, Takahashi will take \lceil N/2 \rceil cards and Aoki will take \lfloor N/2 \rfloor cards.

Takahashi plays optimally to maximize (Takahashi's score) - (Aoki's score), and Aoki plays optimally to minimize (Takahashi's score) - (Aoki's score). Find (Takahashi's score) - (Aoki's score) when both players play optimally.

Constraints

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq A_i \leq 10^9
  • All inputs are integers

Input

N
A_1 A_2 \ldots A_N
  • The first line contains an integer N representing the number of cards.
  • The second line contains N integers A_i (i = 1, 2, \ldots, N) written on card i, separated by spaces.

Output

Output in a single line, as an integer, the value of (Takahashi's score) - (Aoki's score) when both players play optimally.

Sample Input 1

3
10 20 30

Sample Output 1

20

Sample Input 2

5
1 2 3 4 5

Sample Output 2

3

Sample Input 3

8
100 50 80 120 90 30 70 60

Sample Output 3

60