To counteract rising unemployment, the government of Byteland has decided to create new jobs. To this end, modern factories will be built, as well as new power plants that will supply the factories with electricity.

Byteland is crossed by a long highway, along which $n$ cities are located. For simplicity, we will number the cities from $1$ to $n$. Each consecutive city is one kilobyte-meter away from the previous one.

Decisions have already been made, and factories will be built in some cities, while power plants will be built in others. For the $i$-th city, we know the value $a_i$. If it is positive, a power plant with an electrical capacity of $a_i$ megawatts will be built in the $i$-th city, and if it is negative, a factory consuming $-a_i$ megawatts will be built in that city. If $a_i = 0$, no construction is planned in that city.

Your task is to design a power grid that allows electricity to be delivered from power plants to factories. For every pair of adjacent cities, you must decide whether a grid segment will be built between them. Electricity can flow from a power plant to a factory if the cities where these buildings are located are directly or indirectly connected by grid segments. The network is correctly designed if the electricity demand for every factory is met. The cost of the network is directly proportional to the total length of the grid segments (in kilobyte-meters).

Write a program that designs the cheapest correct power grid.

Input

The first line of input contains an integer $n$ ($1 \le n \le 500\,000$), representing the number of cities in Byteland.

The second line contains a sequence of $n$ integers $a_1, \dots, a_n$ ($-10^9 \le a_i \le 10^9$) representing the energy production or consumption in the buildings for consecutive cities.

Output

The output should contain a single line with the minimum cost of a correct power grid. If no correct power grid exists, output $-1$.

Examples

Input 1

17
2 -5 0 2 0 0 0 4 0 0 -1 4 0 0 0 0 -3

Output 1

12

Note

The example below illustrates a test case containing $n = 17$ cities, in which three factories (white circles) and four power plants (black circles) will be built. A correct power grid with a length of 12 kilobyte-meters (gray segments) is also marked.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 2 5 2 4 1 4 3

Subtasks

In some test groups, $n \le 5000$.