Cho một dãy số nguyên ~A~ gồm ~N~ phần tử ~(3 \le N \le 10^6)~ trong đó mỗi phần tử có giá trị tuyệt đối nhỏ hơn ~10^9~.

Yêu cầu

In ra màn hình số cách chọn cặp chỉ số ~i~ và ~j~ sao cho ~1 \le i < j < N~. Các chỉ số ~i, j~ chia dãy ~A~ thành ba đoạn liên tiếp, sao cho tổng các phần tử của mỗi bằng nhau, biết rằng:

• Đoạn ~1~: các phần tử từ vị trí ~1~ đến ~i~;
• Đoạn ~2~: các phần tử từ vị trí ~i + 1~ đến ~j~;
• Đoạn ~3~: các phần tử từ vị trí ~j + 1~ đến ~N~.

Dữ liệu đầu vào

Gồm hai dòng:

• Dòng thứ nhất chứa số nguyên ~N~.
• Dòng thứ hai chứa ~N~ số nguyên.

Dữ liệu đầu ra

Gồm một số nguyên duy nhất là số cách chọn cặp ~(i, j)~ thoả yêu cầu đề bài.

Ví dụ

Ví dụ 1

INPUT

5
1 2 3 0 3

OUTPUT

2

Giải thích: Có ~2~ cách chọn ~(i, j)~:

• Cách ~1~: ~i = 2, j = 3~;
• Cách ~2~: ~i = 2, j = 4~.