有名問題で、過去にもいくつか出題例があると思います。

以下 \(C\) は sort されているとします。

---

\(A\) を \(C\) の並べ替えとします。各 \(i\) について \(A_i\) と \(A_{i+1}\) がそれぞれどちらかが \(+\) の寄与、どちらかが \(-\) の寄与をします。

自明な条件として \(+\) が \(N-1\) 回、 \(-\) が \(N-1\) 回されます。そして、各 \(A_i\) について寄与の和は \(-2\) から \(2\) のいずれかの値をとり、奇数であるものは両端の \(2\) つで、それ以外の寄与の和は偶数です。 （☆）

直感的にはなるべく大きい値を \(+\) して、なるべく小さい値を \(-\) したいです。

---

以下、寄与を並べた列を \(B\) とします。求めたいものは \(S = \displaystyle \sum_{1 \le i \le N} B_i \times C_i\) の最大値です。

\(N\) が偶数のとき

☆を満たすような配列 \(B\) で、もっとも \(S\) が大きくなるものは

\[B = (-2, \dots, -2, -1, 1, 2, \dots, 2)\]

です。そして、この \(B\) が実際に実現可能であることも確かめられます。

\(N\) が奇数のとき

奇数の要素は \((1, 1)\) か \((-1, -1)\) のどちらかです。（ \((1, -1)\) だと \(+\) の総和が偶数であることに矛盾します）

前者では

\[B = (-2, \dots, -2, 1, 1, 2 \dots , 2)\]

後者では

\[B = (-2, \dots, -2, -1, -1, 2 \dots , 2)\]

の時 \(S\) が最大になり（ \(2, -2\) の個数はそれぞれ、総和が \(N-1\) になるようにします）、この \(B\) が実際に実現可能であることも確かめられます。

よって、これらの大きい方を答えとすればよいです。

---

補足

それぞれ、「 \(S\) が最大になる」のは、かなり自然な貪欲であるため、明らかだと思います。このような \(B\) が実際に実現可能であることも、奇数である項を両端に配置することに注意すれば、自然に構築できると思います。

---

実装例

n = int(input())
c = list(map(int, input().split()))
c.sort()

if n % 2 == 0:
    b = [-2] * (n//2-1) + [-1, 1] + [2] * (n//2-1)
    print(sum(x * y for x, y in zip(b, c)))
else:
    b1 = [-2] * (n//2) + [1, 1] + [2] * (n//2-1)
    b2 = [-2] * (n//2-1) + [-1, -1] + [2] * (n//2)
    a1 = sum(x * y for x, y in zip(b1, c))
    a2 = sum(x * y for x, y in zip(b2, c))
    print(max(a1, a2))