Problem F. 构造数组

时间限制：3s
空间限制：256MB

题目描述

给定一个长度为 \(n\) 的整数数组 \(m_1,m_2,…,m_n\)。

现在，请你构造一个数组 \(a_1,a_2,…,a_n\)。

对于构造的数组，有以下两点要求：

1.\(\forall i \in [1,n]\)，\(1 \leq a_i \leq m_i\) 成立。
2.\(\forall i \in [1,n]\), 不存在数对 \(j,k\) 同时满足 \(j < i < k\) 且 \(a_j > a _i < a_k\)。

请输出满足要求的数组所有元素之和的 最大值 。

输入格式

第一行包含整数 \(n\)。

第二行包含 \(n\) 个整数 \(m_1,m_2,…,m_n\)。

输出格式

输出 \(1\) 个整数，表示你构造出的数组 \(a_1,a_2,…,a_n\) 所有元素的和。

输入样例1

5
1 2 3 2 1

输出样例1

9

样例解释

满足题目要求所构造出的数组为：1 2 3 2 1，所有元素之和为9

输入样例2

50
3611 17892460 659500561 1638 1 20734272 29149 795267 169 261662801 4 8 8353 9861 1423 74488485 120 918499 14 33468 636257510 2301 46778 90 4977 90 5 3 3102 52297801 1885 58627 88687594 28 757567 83971972 504682 667465 101201474 243 39503 42953768 906699472 628 93843302 9 89488453 418227 923225 951578

输出样例2

949695744

数据范围

\(1 \leq n \leq 5 \times 10^5, 1 \leq m_i \leq 10^9\)
请注意，答案 可能超出32位整数的范围 。