Trong chuỗi hoạt động hội trại thành lập 35 năm trường chuyên. Liên khối chuyên Tin tổ chức trò chơi Teambuilding như sau: cho ~N~ bạn học sinh được xếp hàng theo thứ tự từ ~1~ đến ~N~, bạn thứ ~i~ tương ứng có mã số ~a_i~ (mã số các bạn được gán ngẫu nhiên, giá trị có thể âm ~|a_i| \leq 10^5~). Nam đại diện cho các anh chị lớp 12 phổ biến luật chơi sau:

Với ~N~ bạn được xếp hàng tương ứng từ ~1~ đến ~N~ như trên, nhiệm vụ các đội chơi tìm ra các cặp chỉ số ~(i,j)~ với tổng các số trong các đoạn ~[1,i-1],[i,j],[j+1,N]~ tương ứng mã số các bạn xếp hàng được tính như sau:

• ~S=a_1+a_2+...+a_{i-1}~;
• ~K=a_i+a_{i+1}+...+a_j~;
• ~T=a_{j+1}+a_{j+2}+...+a_n~;

Thỏa mãn các điều kiện:

• ~1 < i \leq j < N~.
• ~S = K = T~.

Các đội chơi sau một hồi tính toán cũng đưa ra được kết quả của trò chơi, để kiểm tra lại chính xác đáp án các đội đưa ra và mở rộng bài toán với số lượng học sinh xếp hàng nhiều hơn. Nam nhờ các bạn lập trình giải bài toán trên.

Yêu cầu: Cho ~N~ và dãy số ~a_1, a_2, ... , a_N~ tương ứng mã số các bạn học sinh được xếp hàng, xác định số cặp ~(i,j)~ thõa mãn yêu cầu bài toán.

Input

Vào từ file văn bản CAU4.INP:

• Dòng đầu tiên gồm ~N~ là số học sinh xếp hàng.
• Dòng thứ hai chứa ~N~ số nguyên ~a_1, a_2, ... , a_N~, ~a_i~ tương ứng với mã số học sinh thứ ~i~ xếp hàng.

Output

Ghi ra file văn bản CAU4.OUT gồm một số nguyên duy nhất là kết quả bài toán.

Scoring

• Subtask ~1~ ~(20\%)~: ~1 \leq N \leq 100; |a_i| \leq 1000~;
• Subtask ~2~ ~(30\%)~: ~1 \leq N \leq 10^3; |a_i| \leq 10^4~;
• Subtask ~2~ ~(50\%)~: ~1 \leq N \leq 10^5; |a_i| \leq 10^5~.

Example input 1

5
1 2 3 0 3

Example output 1

2

Example input 2

4
0 1 -1 0

Example output 2

1

Example input 3

2
4 1

Example output 3

0