思路

给定一个正整数数组，把它分成三份非空子集，记三份的和为 w1,w2,w3，求表达式 |w1-w2| + |w2-w3| 的最大值。

设三份和按从小到大是 x, y, z。考虑三种情况：

1. w2是最大的一份 z：结果是 3*z - S，其中 S 是总和。要让它大，应该让 z 尽可能大，即把最小的两个元素各自单独成组，其余所有数作为 z。
2. w2是最小的一份 x：结果是 S - 3*x，x 取数组最小值。
3. w2是中间项 y：结果是 z - x，也就是最大和减去最小和。令最小和取最小元素，最大和取除去最小两个元素后的剩余。

题目内容

$Tk$ 有一个长度为 $n$ 的整数数组 ${a_1,a_2,…,a_n}$ ;

他希望将这些元素分成三份，要求每个元素恰好属于其中一份，且三份都不为空；

记第 $i$ 份的元素和为 $w_i(i=1,2,3)$；

请你计算表达式 $∣w_1-w_2∣+∣w_2-w_3∣$的最大可能值。

输入描述

第一行输入一个整数 $n(3≤n≤2×10^9)$，表示数组大小；

第二行输入 $n$ 个整数 $a_1,a_2,...,a_n(1≤a_i≤10^9)$，表示数组元素。

输出描述

输出一个整数，表示最大值 $∣w_1-w_2∣+∣w_2-w_3∣$。

样例1

输入

4
1 2 3 4

输出

11

说明

在这个样例中，将最小的两个元素各自单独分组，剩余元素放在中间一份，可以得到最大值 $11$。