P9097 [PA 2020] Power Plants and Factories

**This problem is translated from [PA 2020](https://sio2.mimuw.edu.pl/c/pa-2020-1/dashboard/) Round 2 [Elektrownie i fabryki](https://sio2.mimuw.edu.pl/c/pa-2020-1/p/ele/).** To deal with the rising unemployment rate, the government of Byteotia decided to create new jobs. For this purpose, modern factories will be built, and new power plants will also be built to supply electricity to the factories. A very long highway runs through Byteotia, and there are $n$ cities along it. For simplicity, we number the cities from $1$ to $n$. Any two neighboring cities are exactly $1$ kilometer apart. It has already been decided that some cities will build factories, and some other cities will build power plants. For the $i$-th city, there is a value $a_i$. If it is positive, then a power plant with capacity $a_i$ megawatts will be built in city $i$. If it is negative, then a factory that consumes $a_i$ megawatts of electricity will be built in that city. If $a_i=0$, then there is no construction plan for that city. Your task is to design a power grid that transmits electricity from power plants to factories. For every pair of neighboring cities, you must decide whether to build a transmission line between them. If a city is connected, directly or indirectly, by transmission lines to some city that has a power plant, then electricity can flow from the power plant to the factory in that city. The design is correct if the electricity demand of every factory is satisfied. The cost of the grid is proportional to the total length (in kilometers) of all transmission lines. Write a program to compute the minimum cost of designing a correct power grid.

The first line contains an integer $n$, the number of cities in Byteotia. The second line contains $n$ integers $a_1,a_2,\cdots,a_n$, describing the production and consumption of electricity in each city.

Output the minimum cost of a correct power grid design. If no correct design exists, output $-1$.

#### Explanation of Sample 1 Below is a sample with $n=17$ cities, where three factories (white circles) and four power plants (black circles) will be built. A correct power grid of $12$ kilometers is marked in gray.  ------------ #### Constraints **This problem uses bundled testdata.** For some subtasks, $n\le 5\times 10^3$. For $100\%$ of the testdata, it is guaranteed that $1\le n\le 5\times 10^5$, $-10^9\le a_i\le 10^9$. Translated by ChatGPT 5