配点 : 900 点
問題文
数列 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
- 所有输入值均为整数
入力
输入是按以下格式从标准输入给出的。
N A_1 A_2 \cdots A_N
出力
打印答案。
入力例 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