题目内容

一位国王拥有 $n$ 袋金币，第 $i$ 袋中的金币数量为 $a_i$。他决定将所有金币袋全部分给三位王子，每位王子至少获得一袋金币，且每袋金币必须完整地分给其中一人。设三位王子最终获得的金币总量分别为 $A,B,C$，请你计算表达式 $|A-B|+|B-C|$ 所能达到的最大值。

元素个数 $n$ 满足 $3 \le n \le 2 \times 10^5$；每袋金币数量 $a_i$ 均为整数且满足 $1 \le a_i \le 10^9$。

输入描述

第一行包含一个整数 $n$，表示金币的袋数。 第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$，依次表示每袋金币的数量。

输出描述

输出一个整数，表示 $|A-B|+|B-C|$ 的最大可能值。

样例1

输入

3
5 5 5

输出

0

说明

所有金币袋的金币数量均为 5，无论怎样分配，三位王子最终获得的金币总量均为 5。因此 $A=B=C=5$，表达式 $|A-B|+|B-C| = 0+0 = 0$，最大值为 0。

样例2

输入

3
1 100 200

输出

299

说明

总金币数为 301，最小袋为 1，次小袋为 100。 一种策略是让 $B$ 获得最少的金币：令 $B=1$，$A$ 和 $C$ 分掉剩余的 300 枚金币（如 $A=200, C=100$），此时表达式 $|A-B|+|B-C| = (200-1)+(100-1)=298$，即 $总额 - 3 \times 最小袋 = 301 - 3 \times 1 = 298$。 另一种策略是让 $B$ 获得最多的金币：令 $A=1$，$C=100$，$B=200$，此时表达式 $|A-B|+|B-C| = (200-1)+(200-100)=199+100=299$，即 $2 \times 总额 - 3 \times (最小袋+次小袋) = 2 \times 301 - 3 \times (1+100) = 299$。 两种策略中取较大值，得到 299。

样例3

输入

5
10 20 30 40 50

输出

210

说明

总金币数为 150，最小袋为 10，次小袋为 20。 第一种策略：让 $B$ 获得最小袋 10，则 $A$ 与 $C$ 之和为 140，表达式值为 $150-3 \times 10 = 120$。 第二种策略：将最小的两袋 10 和 20 分别分给 $A$ 和 $C$，剩余的 120 枚金币全部归于 $B$，此时 $B$ 最大，表达式 $|A-B|+|B-C| = 2 \times 120 - (10+20) = 210$，也等于 $2 \times 150 - 3 \times (10+20) = 210$。 最大值取 210。