K - Sum - |Max - Min|

2 secs 1024 MB
kusirakusira's icon kusirakusira

配点 : 300点

問題文

長さ NN の正数列 AA があり、i(1iN)i(1≦i≦N) 番目の要素は AiA_i です。
くしらくんは AA の空ではない部分列 BB を自由に選びます。

  • sum(B)max(B)min(B)\mathrm{sum}(B) - |\mathrm{max}(B) - \mathrm{min}(B)|

をスコアと定めたときの、スコアの最大値を答えてください。

ただし、数列 XX に対して、sum(X),max(X),min(X)\mathrm{sum}(X), \mathrm{max}(X), \mathrm{min}(X) を以下のように定めます。

  • sum(X):=(数列Xの要素の総和)\mathrm{sum}(X) := (数列 X の要素の総和)
  • max(X):=(数列Xの要素の最大値)\mathrm{max}(X) := (数列 X の要素の最大値)
  • min(X):=(数列Xの要素の最小値)\mathrm{min}(X) := (数列 X の要素の最小値)

制約

  • 1N2×1051≦N≦2×10^5
  • 0Ai1090≦A_i≦10^9
  • 入力はすべて整数

入力

入力は以下の形式で標準入力から与えられる。

NN
A1A_1 A2A_2 \ldots ANA_N

出力

答えを出力してください。


入出力例1

入力
4
3 5 1 2
出力
7

3,5,23, 5, 2 を選ぶとスコアは 7=(10(52))7=(10-(5-2)) となり最大です。


入出力例2

入力
3
1 10 100
出力
100

入出力例3

入力
5
0 0 0 0 0
出力
0

どのように選んでもスコアは変わりません。

Submit


Go (1.21)