問題文

数列 a=(a_1,a_2,\cdots,a_k) に対し，f(a) を以下のように定めます．

• f(a)=\sum_{1 \leq i \leq k} \min(a_1,a_2,\cdots,a_i)

長さ N の整数列 A=(A_1,A_2,\cdots,A_N) が与えられます．

整数列 A を 2 つの（連続とは限らない）（空でもよい）部分列に分解し，それらを X_1,X_2 とおきます． 分解の際，A の各要素がちょうど 1 つの部分列に含まれるようにします． f(X_1)+f(X_2) としてありうる最大値を求めてください．

制約

• 1 \leq N \leq 500000
• 1 \leq A_i \leq 10^9
• 入力される値はすべて整数

入力例 1

6
5 3 6 1 4 7

出力例 1

23

例えば，X_1=(5,3,1),X_2=(6,4,7) と分解すると，f(X_1)+f(X_2)=9+14=23 になります． 23 より大きい値は達成できないため，これが答えです．

入力例 2

10
22 7 20 26 1 11 7 1 15 10

出力例 2

104

入力例 3

15
140039457 164832983 239276621 245532751 274195604 320064892 499774361 419370025 249168130 521915711 744280520 561032101 857077284 543856068 910500852

出力例 3

4618736183

入力例 4

20
596982638 713892371 987307025 722757772 759622047 853214705 628902494 623807668 755031424 486834509 272961036 423817262 434140395 284114341 88860862 222135106 69837030 210989591 225447688 86416231

出力例 4

9047041486