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

入力は以下の形式で標準入力から与えられる． > $ N $ $ A_1 $ $ A_2 $ $ \cdots $ $ A_N $

答えを出力せよ．

### Sample Explanation 1 例えば， $ X_1=(5,3,1),X_2=(6,4,7) $ と分解すると， $ f(X_1)+f(X_2)=9+14=23 $ になります． $ 23 $ より大きい値は達成できないため，これが答えです． ### Constraints - $ 1 \leq N \leq 500000 $ - $ 1 \leq A_i \leq 10^9 $ - 入力される値はすべて整数