← 返回题目列表

AtCoder · jsc2024_final_d

D. 前缀最小值总和的最大值

中文机器翻译题面 查看原题

配点 : 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