Cho dãy số nguyên ~A~ gồm ~N~ phần tử ~A_1, A_2, ..., A_N~. Hãy tìm số cặp chỉ số ~i, j~ thỏa mãn: ~ \sum_{p=1}^{i} A_p = \sum_{q=j}^{N} A_q ~ với ~ 1 \le i < j \le N ~

(Tức là tổng tiền tố đến ~i~ bằng tổng hậu tố từ ~j~ đến hết, với điều kiện chỉ số ~i~ đứng trước ~j~).

Input ESEQ.INP

• Dòng đầu là số nguyên dương ~N~ (~2 \le N \le 10^5~).
• Dòng tiếp theo chứa ~N~ số nguyên ~A_1, A_2, ..., A_N~ (~|A_i| < 10^9~), các số cách nhau một dấu cách.

Output ESEQ.OUT

Số cặp tìm được.

Giới hạn

• Có 50% số test ứng với ~N \le 1000~.
• Có 50% số test còn lại không có giới hạn gì thêm.

Ví dụ:

ESEQ.INP

3
1 0 1

ESEQ.OUT

3