Making a Good Array

Call an array good if one of its elements is equal to the sum of all the other elements. For instance, $a = [1, 2, 3, 6]$ is good because $1+2+3=6$.

Given an array $A$ of length $N$, count the number of ways to remove exactly two elements so that the remaining array is good.

For instance, for $a = [1, 3, 6, 8, 9]$, removing the first and fourth elements leaves $[3, 6, 9]$, where $3+6=9$. Removing the second and third elements leaves $[1, 8, 9]$, where $1+8=9$. Therefore there are 2 valid ways.

The first line contains the length $N$ of the array.

The second line contains the integers $A_1, A_2, \cdots, A_N$, separated by spaces.

Print the number of ways to remove exactly two elements so that the remaining array is good.

• $5 \le N \le 500,000$
• $1 \le A_i \le 1,000,000$
• Each $A_i$ is an integer.
• The sum can exceed the range of a 32-bit integer, so use 64-bit integers.