题目名称：国际象棋锦标赛 (Шаховски турнир)

来源：Macedonian Programming Contests (马其顿编程竞赛)

题目描述

在斯科普里将举办一场国际象棋锦标赛，共有 $N$ 名选手参加（$N$ 总是 $2$ 的幂，$N=2^k$）。每位选手都有一个自然数表示的评分（Rating）。

比赛采用单败淘汰制：

1. 选手两两配对进行第一轮比赛（第1名对第2名，第3名对第4名……）。
2. 评分高者晋级下一轮，评分低者淘汰。若评分相同，随机产生胜利者。
3. 每一场比赛的**分差（Gap）**定义为：胜者评分 - 败者评分。
4. 组织者发现，如果所有比赛的分差之和最大，那么支付给选手的奖金总额就最少。

你可以自由安排选手的初始出场顺序。你的任务是找到一种排列方式，使得整个锦标赛中所有比赛的分差之和达到最大。

示例说明

假设选手评分为：2800, 2500, 2000, 1800, 1600, 1500, 1200, 800。 若按某种顺序排列，总分差之和可能为 5000；但如果交换评分 800 和 2000 的选手位置，总分差之和可以提升至 5800。

输入格式

• 第一行：一个整数 $N$ ($4 \le N \le 2^{19}$)，表示选手人数。
• 第二行：$N$ 个整数 $R_i$ ($1 \le R_i \le 10^9$)，表示选手的评分。输入数据已按非递增顺序（从大到小）排列。

输出格式

• 输出一个整数，代表最优排列下的最大分差总和。

限制要求

• 时间限制：300 毫秒
• 内存限制：1 兆字节 (1 MB)
• 注意：由于内存限制极小，$2^{19}$ 个 int 占用约 2MB，因此你不能存储整个数组，必须边读边算或使用更小的数据类型。

样例 1：标准 8 人赛（题目配图对应的最优解）

此样例验证基础逻辑：最大分差总和 = 前 4 名之和 - 后 4 名之和。

输入 (1.in)

8
2800 2500 2000 1800 1600 1500 1200 800

输出 (1.out)

5800

(计算过程：(2800+2500+2000+1800) - (1600+1500+1200+800) = 9100 - 5100 = 4000... 抱歉，刚才口算有误，按照题目逻辑：冠军贡献 3 次，其余人根据被淘汰轮次贡献。公式简化后确实为：$R_1 + R_2 + R_3 + R_4 - R_5 - R_6 - R_7 - R_8$)

样例 2：最小规模 4 人赛（含重复分值）

验证当存在相同评分以及最小 $N$ 时的处理。

输入 (2.in)

4
1000 1000 500 200

输出 (2.out)

1300

(计算过程：(1000 + 1000) - (500 + 200) = 1300)

样例 3：16 人赛（测试 long long 累加）

验证较大 $N$ 下的求和稳定性。

输入 (3.in)

16
100 95 90 85 80 75 70 65 60 55 50 45 40 35 30 25

输出 (3.out)

640

(计算过程：前 8 项之和 640，后 8 项之和 340。$640 - 340 = 300$。不对，公式应为前 8 项减后 8 项：$(100+95+90+85+80+75+70+65) - (60+55+50+45+40+35+30+25) = 660 - 340 = 320$。)