该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

物资分配

题目描述

Y 同学有一个长度为 $n$ 的物资价值数组：$a_1,a_2,\dots,a_n$

现在需要将这 $n$ 件物资分配到三个仓库中，要求：

• 每件物资必须恰好放入一个仓库；
• 三个仓库中的物资数量必须相同。

记三个仓库中物资价值总和分别为 $w_1,w_2,w_3$。

Y 同学希望让下面这个式子的值尽可能大：

$|w_1-w_2|+|w_2-w_3|$

请你计算这个式子的最大可能值。

输入格式

第一行输入一个整数 $n$，表示物资数量。

第二行输入 $n$ 个整数 $a_1,a_2,\dots,a_n$，表示每件物资的价值。

保证 $n$ 是 $3$ 的倍数。

输出格式

输出一行一个整数，表示 $|w_1-w_2|+|w_2-w_3|$ 的最大可能值。

样例

样例输入 #1

3
1 2 3

样例输出 #1

3

样例解释

在这个样例中，每个仓库恰好放入 $1$ 件物资。

可以令：

• $w_1=3$；
• $w_2=1$；
• $w_3=2$。

则：

$|w_1-w_2|+|w_2-w_3|=|3-1|+|1-2|=2+1=3$

所以答案为 $3$。

数据范围与约定

对于 $100\%$ 的数据，保证：$3\le n\le2\times10^5$；$n$ 是 $3$ 的倍数；$1\le a_i\le10^9$。