Power Grid Optimization

To counter the rising unemployment rate, the government of Byteotia has planned to build modern factories and new power plants along a long highway. Along this highway there are n cities arranged in a line (cities are numbered from 1 to n with a distance of 1 km between consecutive cities). For each city i an integer a_i is given:

• If a_i > 0, a power plant with a capacity of a_i megawatts will be built at that city.
• If a_i < 0, a factory that consumes |a_i| megawatts will be built.
• If a_i = 0, no construction is planned.

You are to design an electrical network by deciding, for every pair of consecutive cities, whether to build a transmission line (which costs 1 km per connection) between them. When a city is connected directly or indirectly with some city containing a power plant, its factory (if any) will be supplied with power.

For the network to be considered valid, every connected segment of cities that contains at least one factory (a_i < 0) must also contain at least one power plant (a_i > 0) and have a nonnegative total capacity (i.e. the sum of a_i over the segment is at least 0). Note that a city (or a connected group of cities) that does not contain any factories does not impose any additional constraints.

The cost of a connected segment is the number of transmission lines built in that segment (a segment of k cities requires k-1 lines). Since all cities are arranged in a line, if you partition the cities into several segments then the total cost is n - (number of segments). Your task is to design a valid electrical network with the minimum total cost. If no valid network exists, output -1.

inputFormat

The first line contains a single integer n (1 ≤ n ≤ 2000) representing the number of cities.

The second line contains n integers a₁, a₂, ..., a_n separated by spaces. Each a_i may be positive, negative, or zero. A positive value indicates a power plant with that capacity, and a negative value indicates a factory with a consumption of |a_i| megawatts.

outputFormat

Output a single integer—the minimum total cost (in km) to build a valid network. If there is no valid network design, output -1.

sample

5
5 -3 -2 0 0

2