Game on a Line

Limits: 2 sec., 256 MiB

This statement was translated automatically from Ukrainian.

To avoid boredom, Zenik and Marichka decided to play an interesting game.

The game takes place on a line where \(n\) points are located. The points are numbered from 1 to \(n\) from left to right. Between each pair of adjacent points, a single integer is written (between the points numbered \(i\) and \(i+1\), the number \(a_i\) is written).

A player has a single token, which initially stands at the point numbered 1. He can move his token from any point to any other point. For this, the player pays a penalty equal to the absolute value of the sum of numbers written between these points. That is, if the token was moved from position \(x\) to position \(y\), then the player pays a penalty of \(|\sum_{i=min\{x,y\}}^{max\{x,y\}-1} a_{і}|\) hryvnias.

The goal of the game is to visit all points. A point is considered visited if the token has been at it at least once. Note that the first point is considered visited right at the beginning of the game.

Zenik wants to impress Marichka with his algorithmic skills. For this, he needs to play optimally (paying the minimum possible penalty amount), but since this task turned out to be too difficult for him, you are the one who has to help him.

Input

The first line contains a single integer \(n\) — the number of points.

The second line contains \(n-1\) integers \(a_i\) — the numbers written between the points.

Output

In a single line, output an integer — the minimum penalty for the game.

Constraints

\(|a_i| \le 10^5\),

32% of tests: \(2 \le n \le 10\),

28% of tests: \(11 \le n \le 20\),

40% of tests: \(21 \le n \le 1000\).

Samples

Input (stdin) сopy	Output (stdout) сopy
6 5 -3 -3 4 -6	11

Notes

One of the possible optimal game scenarios:

\(1 \rightarrow 4 \rightarrow 6 \rightarrow 3 \rightarrow 5 \rightarrow 2\).

Penalty for moving the token between the first and fourth points is 1 hryvnia.

Penalty for moving the token between the fourth and sixth points is 2 hryvnias.

Penalty for moving the token between the sixth and third points is 5 hryvnias.

Penalty for moving the token between the third and fifth points is 1 hryvnia.

Penalty for moving the token between the fifth and second points is 2 hryvnias.

Thus, the total penalty is 11 hryvnias.