min

题目描述

起始时数轴上有 n 个不同位置的点 $x_1,x_2,...,x_n$。

你可以进行以下操作任意次（包括零次）:

• 选择一个 $i (1 \leq i \leq N-3)$，设 mid 为将第 i,i+1,i+2,i+3 升序排列下第 1 个和第 4 个坐标的中点，然后将第 2 个和第 3 个分别移动到与 mid 对称的位置。

可以证明，无论如何重复执行，所有点的坐标还是不同的。

求任意次操作过后所有点坐标之和的最小值。

输入格式

第一行一个整数 n。

第二行 n 个整数表示坐标。

输出格式

输出一行一个数表示答案。

样例 #1

样例输入 #1

4
1 3 9 10

样例输出 #1

21

样例 #2

样例输入 #2

6
1 2 7 11 15 20

样例输出 #2

54

提示

样例一解释

对于 (1,3,9,10) 如果不换，坐标和为 1+3+9+10=23。

如果进行一次操作，中点 mid=(1+10)/2=5.5，则 3 换到对称位置 8，9 换到对称位置 2，此时坐标和为 1+2+8+10=21。

数据范围

对于 30% 的数据，n<=100,0<=xi<=1000；

对于100% 的数据， n<=2e5,0<=xi<=1e12。