3SUM là một bài toán thuật toán nổi tiếng, trong đó với một dãy số nguyên cho trước $c_1, c_2, \dots, c_m$, ta cần tìm ba chỉ số $i < j < k$ sao cho $c_i + c_j + c_k = 0$.
Hiện chưa có lời giải nào cho bài toán này với các dãy số nguyên bất kỳ có độ phức tạp tốt hơn đáng kể so với $O(m^2)$. May mắn thay, Bajtek không biết điều đó và đã quyết định giải bài toán này cho "Dãy số rất yêu thích" của mình.
Dãy số yêu thích của Bajtek bao gồm $n$ số nguyên $a_1, a_2, \dots, a_n$. "Dãy số rất yêu thích" của Bajtek được tạo ra bằng cách xét tất cả $\frac{n(n+1)}{2}$ đoạn con liên tiếp của dãy số yêu thích, tính tổng các phần tử trong mỗi đoạn và đưa tất cả các tổng này vào một dãy mới (có tính đến các giá trị lặp lại). Các tổng của các đoạn được sắp xếp theo thứ tự tăng dần của chỉ số bắt đầu đoạn, và trong trường hợp chỉ số bắt đầu bằng nhau, chúng được sắp xếp theo thứ tự tăng dần của chỉ số kết thúc đoạn.
Để mọi thứ không quá đơn giản, Bajtek không quan tâm đến việc tìm bộ ba chỉ số $i < j < k$. Anh ấy muốn biết chính xác số lượng tất cả các bộ ba chỉ số $i < j < k$ tương ứng với các phần tử có tổng bằng không. Hãy giúp anh ấy viết một chương trình tính toán số lượng các bộ ba như vậy!
Dữ liệu vào
Dòng đầu tiên của đầu vào tiêu chuẩn chứa một số nguyên $n$ ($1 \le n \le 500$), biểu thị độ dài của Dãy số yêu thích của Bajtek.
Dòng tiếp theo chứa $n$ số nguyên $a_i$ ($|a_i| \le 20\,000$), biểu thị các phần tử liên tiếp của Dãy số yêu thích của Bajtek.
Dữ liệu ra
Dòng đầu tiên và duy nhất của đầu ra tiêu chuẩn phải chứa một số nguyên duy nhất – số lượng các bộ ba chỉ số $i < j < k$ tương ứng với các phần tử của Dãy số rất yêu thích của Bajtek có tổng bằng 0.
Ví dụ
Ví dụ 1
3 7 -4 -2
1
Ví dụ 2
10 0 0 0 0 0 0 0 0 0 0
26235
Ghi chú
Trong ví dụ đầu tiên, Dãy số rất yêu thích là $[7, 3, 1, -4, -6, -2]$, và bộ ba duy nhất có tổng bằng 0 là $3 + 1 + (-4)$, do đó kết quả là 1.
Trong ví dụ thứ hai, Dãy số rất yêu thích của Bajtek bao gồm năm mươi lăm số không. Với bất kỳ ba chỉ số $i < j < k$ nào, tổng các phần tử tương ứng đều bằng 0, và có tất cả $26\,235$ bộ ba như vậy.