Sushi

問題文

無事フル単を達成した処理犬君は、自分へのご褒美にお寿司屋さんにやってきました。
そのお寿司屋さんは、 $N$ 個の寿司ネタを提供しており、 $1,2,3,\dots,N$ の番号が付いています。
また、寿司ネタ $i \, (1 \leq i \leq N)$ 美味しさは $A_i$ と定められています。

そのお寿司屋さんでは、好きな寿司ネタを $3$ つ (同じ寿司ネタを $2$ つ以上選んでも良い。) 選んで注文することで、お得にお寿司が食べられるキャンペーンをやっています。処理犬君は、早速寿司ネタを $3$ つ選ぼうと思いましたが、どれも美味しそうで中々決められません。
そこで、処理犬君は、以下で定義される「満足度」を最大化するように寿司ネタを $3$ つ選ぶことにしました。処理犬君が得られる満足度の最大値を出力してください。

満足度

寿司ネタ $i,j,k$ を選んだときの満足度は、
$(A_i + A_j + A_k) \times$ (集合 $\{i,j,k\}$ の要素の種類数) です。
例えば、 $A_1 = 10, A_2 = 20, A_3 = 30$ で、

• $(i = 1, j = 2, k = 3)$ を選んだときの満足度は、
  $(10 + 20 + 30) \times$ (集合 $\{1,2,3\}$ の要素の種類数) $= (10 + 20 + 30) \times 3 = 180$ です。
• $(i = 1, j = 3, k = 3)$ を選んだときの満足度は、
  $(10 + 30 + 30) \times$ (集合 $\{1,3,3\}$ の要素の種類数) $= (10 + 30 + 30) \times 2 = 140$ です。
• $(i = 3, j = 3, k = 3)$ を選んだときの満足度は、
  $(30 + 30 + 30) \times$ (集合 $\{3,3,3\}$ の要素の種類数) $= (30 + 30 + 30) \times 1 = 90$ です

制約

• $1 \leq N \leq 2 \times 10^5$
• $-10^8 \leq A_i \leq 10^8 \, (1 \leq i \leq N)$
• 入力は全て整数

入力

N
A_1 A_2 A_3 ... A_N

• $1$ 行目に、提供している寿司ネタの数 $N$ が与えられます。
• $2$ 行目に、各寿司ネタの美味しさ $A_i \, (1 \leq i \leq N)$ が空白区切りで与えられます。

出力

処理犬君が得られる満足度の最大値を出力してください。

入力例 1

3
10 20 30

出力例 1

180

寿司ネタ $1,2,3$ を選んだとき、得られる満足度は、
$(10 + 20 + 30) \times$ (集合 $\{1,2,3\}$ の要素の種類数) $= (10 + 20 + 30) \times 3 = 180$ です。 満足度を $180$ より大きくするように寿司ネタを選ぶことはできないので、 $180$ を出力します。

入力例 2

1
10

出力例 2

30

提供されている寿司ネタが $3$ 個未満の場合もあります。

入力例 3

1
-1

出力例 3

-3

美味しさが負の値のこともあります。