Chia đoạn                                                Tên file: SUBARR.CPP

Bạn được cho trước một dãy số nguyên a₁, a₂, …, a_n.

Đếm số cách chia dãy thành 3 đoạn mà các phần tử trong mỗi đoạn là liên tiếp nhau, sao cho tổng các phần tử của mỗi đoạn là bằng nhau.

Nói cách khác, đếm số cặp (i,j) (2 ≤ i ≤ j ≤ n) sao cho:

INPUT: SUBARR.INP

• Dòng 1: chứa số nguyên dương n (1 ≤ n ≤ 5*10⁵)
• Dòng 2: chứa n số nguyên a[1], a[2], …, a[n] (|a[i]| ≤ 10⁹)

OUTPUT: SUBARR.OUT

• Một dòng duy nhất chứa giá trị là số cách phân chia dãy số

Ví dụ