题目描述

给定一个整数序列 $a_1,\dots,a_n$ ，小爱需要通过一系列调整操作将所有数字改成 $0$。每步调整操作中，小爱可以选择一段连续的区间（也可以只选一个数），将所选的全部数字增加一单位，或将所选的全部数字减少一单位。

请问小爱最少需要几步操作才能将所有数字改成 $0$？

输入格式

第一行：单个整数表示 $n$； 第二行：$n$ 个整数表示 $a_1,\dots,a_n$。

输出格式

单个整数：表示最少调整次数

数据范围

• 对于 $30\%$ 的数据，$1\leq n\leq 20$，$-20\leq a_i\leq 20$；
• 对于 $60\%$ 的数据，$1\leq n\leq 2000$，$-2000\leq a_i\leq 2000$；
• 对于 $100\%$ 的数据，$1\leq n\leq 500,000$，$-10^{9}\leq a_i\leq 10^9$

样例数据

输入:

4
1 1 1 2

输出:

2

说明:

第一步将所有数字减一，第二步将最后一个数字减一

输入:

3
-1 1 -1

输出:

3