2746번 - 좋은 배열 만들기

배열의 어떤 원소가 다른 모든 원소의 합과 같을 때, 이러한 배열을 "좋은 배열"이라고 하자. 예를 들어 배열 $a = [1,\ 2,\ 3,\ 6]$은 $1+2+3=6$이기 때문에 "좋은 배열"이다.

길이가 $N$인 배열 $A$가 주어지면, 정확히 2개의 원소를 제거해서 "좋은 배열"을 만드는 방법의 수를 구해보자.

예를 들어 $a = [1,\ 3,\ 6,\ 8,\ 9]$의 경우, 첫째 원소와 넷째 원소를 제거하면 $3+6=9$를 만족하고, 둘째 원소와 셋째 원소를 제거하면 $1+8=9$를 만족하므로 정답은 2이다.

첫째 줄에 배열의 길이 $N$이 주어진다.

둘째 줄에 배열의 원소 $A_1, A_2, \cdots, A_N$이 공백으로 구분되어 주어진다.

정확히 2개의 원소를 제거해서 "좋은 배열"을 만들 때, 원소를 제거하는 방법의 수를 출력한다.

• $5 \leq N \leq 500\,000$
• $1 \leq A_i \leq 1\,000\,000$, $A_i$는 정수
• 32bit 정수를 사용하는 경우 overflow가 발생할 수 있음에 주의하자.