Độ khó: Khá (3/4 điểm)

📖 Bài giải chi tiết: 👉 Bấm vào đây để xem lời giải cụ thể của bài này trên blog

⚠️ Lưu ý: hãy đảm bảo em đã thật sự cố gắng tự làm bài trước, rồi mới bấm vào xem bài giải nhé!

🎓 Khóa học Lập trình Thuật toán thi đấu của thầy Nguyễn Việt Nam Sơn – 111 buổi video, kèm cặp cá nhân, luyện thi chuyên Tin · HSG Tin học · Tin học trẻ · đội tuyển quốc gia · Olympic/ICPC. 👉 Xem chi tiết khóa học · Thành tích học viên

📞 Đăng ký học: Zalo 0767 666 702 · Facebook Nguyễn Việt Nam Sơn · 🌐 laptrinhthuattoan.blogspot.com

Lưu ý: Trên web đọc dữ liệu từ bàn phím (stdin) và in ra màn hình (stdout).

Cho dãy số nguyên ~A = (a_1, a_2, \ldots, a_n)~. Hãy đếm số cách chia dãy trên thành 4 dãy con gồm các số liên tiếp của ~A~ sao cho tổng các số trong mỗi dãy con đều bằng nhau. Chính xác hơn, mỗi cách chia được mô tả bằng bộ 3 chỉ số ~(i, j, k)~: ~1 \le i < j < k < n~. Trong đó ~(a_1, a_2, \ldots, a_i)~ là dãy 1; ~(a_{i+1}, a_{i+2}, \ldots, a_j)~ là dãy 2; ~(a_{j+1}, a_{j+2}, \ldots, a_k)~ là dãy 3 và ~(a_{k+1}, a_{k+2}, \ldots, a_n)~ là dãy 4.

Hai cách chia khác nhau ứng với hai bộ 3 chỉ số ~(i, j, k)~ khác nhau.

Dữ liệu vào

• Dòng đầu tiên ghi số nguyên dương ~N~ ~(N \le 10^6)~.
• Dòng thứ hai ghi ~N~ số nguyên ~a_1, a_2, \ldots, a_n~ ~(|a_i| \le 10^9;\ i = 1, 2, \ldots, n)~; hai số liên tiếp cách nhau bằng một dấu trống.

Kết quả

• Ghi ra một số nguyên là số lượng cách chia tìm được.

Giới hạn

• 20% số test có ~N \le 50~.
• 20% số test có ~N \le 500~.
• 30% số test có ~N \le 5000~.
• 30% số test có ~N \le 10^6~.

Sample Input 1

8
1 1 1 1 1 1 1 1

Sample Output 1

1

Giải thích

Dãy có 8 số 1, tổng là ~8~, nên mỗi dãy con phải có tổng ~8 / 4 = 2~, tức là mỗi dãy con gồm đúng 2 số 1. Chỉ có một cách duy nhất là cắt sau vị trí ~i = 2~, ~j = 4~, ~k = 6~: ~(1, 1)\ |\ (1, 1)\ |\ (1, 1)\ |\ (1, 1)~. Vậy đáp án là 1.