题目内容

在算法课上，老师给出了一个长度为 $n$ 的整数序列 $b_1, b_2, \dots, b_n$。你需要将每个元素恰好分配到三个非空的组 $A, B, C$ 中，记三个组的元素和分别为 $S_A, S_B, S_C$。请你计算 $|S_A - S_B| + |S_B - S_C|$ 可能达到的最大值。序列长度 $n$ 满足 $3 \le n \le 2\times 10^5$，每个元素 $b_i$ 均为正整数且 $1 \le b_i \le 10^9$。

输入描述

第一行输入一个整数 $n$，表示序列的长度。第二行输入 $n$ 个整数，依次为 $b_1, b_2, \dots, b_n$，相邻整数之间用空格分隔。

输出描述

输出一个整数，表示 $|S_A - S_B| + |S_B - S_C|$ 的最大可能值。