Dividing an Array#509

Dividing an Array

0.5 seconds
256 megabytes
Hard

You are given an array of integers . You put it into a magical bag. You can perform the following operation any (possibly zero) number of times:

  1. take a non-empty array from the bag;

  2. choose any element of the array b_i;

  3. remove b_i, splitting the array into two (possibly empty) arrays;

  4. put the two new arrays back into the bag.

Find the minimum number of operations required so that in the end, in each array from the bag, every segment of length greater than has a non-negative sum.

Input

The first line contains a single integer (1 \le n \le 10^5) — the length of the array .

The second line contains integers a_i (-10^6 \le a_i \le 10^6) — the description of the array .

Output

Output a single integer — the minimum number of operations required so that in the end, in each array from the bag, every segment of length greater than has a non-negative sum.

Examples

Example 1

Loading
Loading

Example 2

Loading
Loading

Note

In the first example, you can, for instance, remove the number , resulting in two arrays and . Note that splitting into the array is allowed because we do not consider segments of length .

In the second example, nothing needs to be removed; the array already satisfies the conditions.

Scoring

In this problem, each block is scored per test case.

  1. ( points): n \leq 10;

  2. ( points): n \leq 100;

  3. ( points): n \leq 2\,000;

  4. ( points): no additional constraints.