Maximize Negative Signs

Assign a plus or minus sign to each element of an array of positive integers so that the signed sum of every non-empty prefix is strictly greater than 0. Maximize the number of minus signs.

输入格式

The first line contains n, and the second line contains n integers. Original bounds: 1≤n≤100000, 1≤a[i]≤10^9; a prefix sum of 0 is invalid.

输出格式

Output a single integer answer.

样例 1

输入：

3
1 1 1

输出：

1

样例 2

输入：

4
5 1 1 1

输出：

3

样例 3

输入：

4
2 3 1 4

输出：

1

样例说明

The outputs of the three public examples are, in order: 1; 3; 1. Verified by independent enumeration or direct simulation.