题目描述

Byteasar has decided to build a house.

He has chosen a very narrow valley as its location.

Before Byteasar starts the actual construction work, he has to level the ground first.

He has two excavators at his disposal: the first one can either increase or decrease the ground level of any connected area in the valley by exactly meters; the other can do the same, i.e., either increase or decrease the ground level of any connected area in the valley, but by exactly meters.

Notice that neither before such an operation nor after it needs the ground in the affected area be actually leveled.

Given a map of the area, determine the minimum number of operations required to level the ground in the whole valley, i.e., to make the ground level everywhere equal 0. While the operations are performed, the ground level at any point in the valley can have arbitrary value; in particular, it may be negative.

输入格式

In the first line of the standard input there are three integers, , , (, ), separated by single spaces.

The number denotes the valley's length in meters.

The second line contains integers, , separated by single spaces.

These numbers, all with absolute value no larger than , represent the initial ground level in meters of successive one meter long slices of the valley.

In tests worth 30% of the points the following conditions hold in addition: and .

In tests worth 60% of the points the following conditions hold in addition: and .

In tests worth 90% of the points the condition holds in addition.

输出格式

In the first and only line of the standard output your program should print a single integer: the minimum number of operations required to level the ground in the whole valley, or if leveling the whole valley with given excavators is impossible.

5 2 3
1 2 1 1 -1

5