Inchworm Cut

Interview

Time limit1sMemory limit1024 MB

Summary

Count the ways to split an array into head, chest, and abdomen segments whose sums satisfy head < abdomen < chest.

Level: Medium5 of 10
Topics: Prefix sum, Two pointers, Array
Solved: No attempts yet

Problem

An inchworm is made of a one-dimensional array of $N$ positive integers. Because it is an insect, its body can be divided into a head, a chest, and an abdomen.

Each part is a contiguous segment of the array. The head is on the left, the chest is in the middle, and the abdomen is on the right. The size of each part is the sum of the values in its segment.

Muji knows that the chest is larger than the abdomen and the abdomen is larger than the head. However, he does not know where the head and chest are separated, or where the chest and abdomen are separated. Help Muji by counting the number of ways the inchworm can be divided. Specifically, count the pairs $X,Y$ that satisfy

$\sum_{i=1}^{X} A_i < \sum_{i=Y+1}^{N} A_i < \sum_{i=X+1}^{Y} A_i$

with $1 \leq X < Y < N$ .

Input

The first line contains the integer $N$ . ( $3 \leq N \leq 1\,000\,000$ )

The second line contains the values $A_1, A_2, \cdots, A_N$ separated by spaces. ( $1 \leq A_i \leq 100\,000$ )

Output

Print the number of ways the inchworm's head, chest, and abdomen can be separated.

Examples1

Example 1
Input
```
5
3 4 12 1 8
```
Expected output
```
4
```