Problem F. 构造数组
该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。
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位整数的范围 。