AT_jsc2024_final_d Max of Sum of Prefix Min

对于数列 $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$ 分成两个（不一定连续）（可以为空）子序列，分别记为 $X_1, X_2$。分割时，$A$ 的每个元素必须恰好属于一个子序列。求 $f(X_1)+f(X_2)$ 的可能最大值。

输入按以下格式从标准输入给出： > $N$ $A_1$ $A_2$ $\cdots$ $A_N$

输出答案。

### 样例解释 1 例如，将 $X_1 = (5,3,1), X_2 = (6,4,7)$ 这样分割，则 $f(X_1)+f(X_2)=9+14=23$。因为无法获得比 $23$ 更大的值，所以这个答案是最优的。 ### 数据范围 - $1 \leq N \leq 500000$ - $1 \leq A_i \leq 10^9$ - 输入的所有数都是整数。 由 ChatGPT 5 翻译