Count Array Splits Where Left Sum Greater Than Right Sum

Given an integer array, count the ways to cut it into two non-empty contiguous parts so that the sum of the left part is strictly greater than the sum of the right part.

Integer sums use arbitrary precision; the standard input/output protocol and the upper bound on n are explicitly supplied by this site.

This site adds a standard input/output protocol.

输入格式

The first line contains n (1 ≤ n ≤ 200000), and the second line contains n integers with absolute values at most 10^9.

输出格式

Output the number of qualifying cuts.

样例 1

输入：

5
-3 -2 1 -6 -30

输出：

4

样例 2

输入：

2
1 1

输出：

0

样例 3

输入：

3
-5 1 1

输出：

0