벌레컷

자벌레는 크기 $N$의 1차원 양의 정수 배열로 이루어져 있다. 자벌레는 곤충이라서 머리, 가슴, 배로 부위를 구분할 수 있다.

각 부위는 배열에서 연속한 구간이다. 머리는 왼쪽, 가슴은 가운데, 배는 오른쪽에 있다. 각 부위의 크기는 해당 구간에 있는 값의 합이다.

무지는 가슴이 배보다 크고 배가 머리보다 크다는 것은 알고 있다. 하지만 머리와 가슴, 가슴과 배가 어느 지점에서 나뉘는지는 모른다. 무지를 도와 자벌레를 나눌 수 있는 경우의 수를 구하자. 구체적으로는 다음 조건을 만족하는 쌍 $X,Y$의 개수를 구한다.

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

단, $1 \leq X < Y < N$이다.

첫 줄에 정수 $N$이 주어진다. ($3 \leq N \leq 1\,000\,000$)

두 번째 줄에 배열의 값 $A_1, A_2, \cdots, A_N$이 공백으로 구분되어 주어진다. ($1 \leq A_i \leq 100\,000$)

자벌레의 머리, 가슴, 배를 나눌 수 있는 경우의 수를 출력한다.