3SUM은 주어진 정수 수열 $c_1, c_2, \dots, c_m$에 대하여 $i < j < k$이면서 $c_i + c_j + c_k = 0$을 만족하는 세 인덱스를 찾는 잘 알려진 알고리즘 문제입니다.

임의의 정수 수열에 대해 이 문제를 $O(m^2)$보다 유의미하게 빠른 복잡도로 해결하는 방법은 알려져 있지 않습니다. 다행히도 Bajtek은 이 사실을 모르고 있으며, 자신의 '매우 좋아하는 수열(Bardzo Ulubiony Ciąg)'에 대해 이 문제를 해결하기로 했습니다.

Bajtek의 '좋아하는 수열'은 $n$개의 정수 $a_1, a_2, \dots, a_n$으로 구성됩니다. Bajtek의 '매우 좋아하는 수열'은 '좋아하는 수열'의 모든 $\frac{n(n+1)}{2}$개의 연속된 구간의 합을 구하고, 이 합들을 하나의 수열로 나열하여 만들어집니다(중복 포함). 구간의 합들은 구간의 시작 인덱스를 기준으로 오름차순으로 정렬하며, 시작 인덱스가 같을 경우 끝 인덱스를 기준으로 오름차순으로 정렬합니다.

문제를 너무 쉽게 만들지 않기 위해, Bajtek은 $i < j < k$인 인덱스 세 개를 직접 찾는 것에는 관심이 없습니다. 그는 합이 0이 되는 원소들에 대응하는 모든 인덱스 세트 $i < j < k$의 정확한 개수를 알고 싶어 합니다. 그를 도와 이 개수를 계산하는 프로그램을 작성하세요!

입력

첫 번째 줄에는 Bajtek의 '좋아하는 수열'의 길이를 나타내는 정수 $n$ ($1 \le n \le 500$)이 주어집니다.

다음 줄에는 Bajtek의 '좋아하는 수열'의 각 원소를 나타내는 $n$개의 정수 $a_i$ ($|a_i| \le 20\,000$)가 주어집니다.

출력

표준 출력의 첫 번째 줄에 Bajtek의 '매우 좋아하는 수열'의 원소들 중 합이 0이 되는 인덱스 세트 $i < j < k$의 개수를 나타내는 정수 하나를 출력합니다.

예제

입력 1

3
7 -4 -2

출력 1

1

입력 2

10
0 0 0 0 0 0 0 0 0 0

출력 2

26235

참고

첫 번째 예제에서 '매우 좋아하는 수열'은 $[7, 3, 1, -4, -6, -2]$이며, 합이 0이 되는 유일한 세 원소의 조합은 $3 + 1 + (-4)$이므로 정답은 1입니다.

두 번째 예제에서 Bajtek의 '매우 좋아하는 수열'은 55개의 0으로 구성됩니다. 임의의 세 인덱스 $i < j < k$에 대해 대응하는 원소들의 합은 0이며, 이러한 세트의 개수는 26,235개입니다.