← 返回题目列表

AtCoder · arc123_d

D. Inc、12 月 - 分解

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

分数: 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).