← 返回题目列表

Codeforces · 596/B

B. 威尔伯和阵列

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

小猪威尔伯又在摆弄数组了。他有数组 a1, a2, ..., an 最初由 n 个零组成。在一步中,他可以选择任何索引 i,并对所有元素 ai, ai + 1, ..., an 加 1,或者从所有元素 ai, ai + 1, ..., an 中减 1。他的目标是最终得到数组 b1, b2, ..., bn。

当然,Wilbur 希望以最少的步骤实现这个目标,并要求你计算这个值。

输入

输入的第一行包含一个整数 n (1 ≤ n ≤ 200 000) — 数组 ai 的长度。最初,每个位置 i 的 ai = 0,因此输入中未给出该数组。

输入的第二行包含 n 个整数 b1, b2, ..., bn (- 109 ≤ bi ≤ 109)。

输出

打印 Wilbur 需要执行的最少步数,以便对所有 i 实现 ai = bi。

示例

输入 #1

5
1 2 3 4 5

输出 #1

5

输入 #2

4
1 2 2 1

输出 #2

3

注意

在第一个样本中,Wilbur可以依次选择索引1、2、3、4和5,并在相应的后缀上加1。

在第二个样本中,Wilbur 首先选择索引 1 和 2,并将相应后缀加 1,然后选择索引 4 并减 1。