分数: 700 点
问题陈述
给定的是整数序列 A = (A_1, \ldots, A_N).
考虑一对整数序列 B = (B_1, \ldots, B_N) 和 C = (C_1, \ldots, C_N) 满足以下条件:
- A_i = B_i + C_i 对于每个都成立 1\leq i\leq N;
- B 是非递减的,即 B_i\leq B_{i+1} 对于每个都成立 1\leq i\leq N-1;
- C 是非递增的,即 C_i\geq C_{i+1} 对于每个都成立 1\leq i\leq N-1.
找到以下的最小可能值 \sum_{i=1}^N \bigl(\lvert B_i\rvert + \lvert C_i\rvert\bigr).
约束
- 1\leq N\leq 2\times 10^5
- -10^8\leq A_i\leq 10^8
输入
输入由标准输入按以下格式给出:
N A_1 A_2 \ldots A_N
输出
打印答案。
示例输入 1
3 1 -2 3
示例输出 1
10
一对序列 B = (B_1, \ldots, B_N) 和 C = (C_1, \ldots, C_N) 产生的最小值是:
- B = (0, 0, 5),
- C = (1, -2, -2).
这里我们有 \sum_{i=1}^N \bigl(\lvert B_i\rvert + \lvert C_i\rvert\bigr) = (0+1) + (0+2) + (5+2) = 10.
示例输入 2
4 5 4 3 5
示例输出 2
17
一对序列 B 和 C 产生的最小值是:
- B = (0, 1, 2, 4),
- C = (5, 3, 1, 1).
示例输入 3
1 -10
示例输出 3
10
一对序列 B 和 C 产生的最小值是:
- B = (-3),
- C = (-7).