题目描述

卫士正在和牢马玩游戏。 现在有 $n$ 堆石子，卫士每次会拿走一整堆石子，牢马每次会从所有还有石子的堆中各拿一个石子，卫士先手，轮流行动。她们都希望自己拿到的石子尽可能多。 我们认为卫士和牢马都会以最优策略进行游戏，请问卫士最后会拿到多少石子？

输入格式

• 第一行输入一个整数 $n$ ($1 \le n \le 2 \times 10^5$)。
• 第二行输入 $n$ 个整数 $a_1, a_2, a_3, \dots, a_n$ ($1 \le a_i \le 10^9$)，代表第 $i$ 堆有 $a_i$ 个石子。

输出格式

输出一个整数，代表卫士最后拿到的石子数量。

样例

样例输入 1

4
1 2 3 4

样例输出 1

6