Phân Chia Đoạn Số

Cho một dãy gồm $n$ số nguyên $v_1, v_2, \ldots, v_n$. Hãy đếm số cách chia tất cả các phần tử của dãy thành ba phần liên tiếp sao cho tổng các phần tử trong mỗi phần đều bằng nhau.

Cụ thể hơn, bạn cần tìm số lượng cặp chỉ số $(i, j)$ thỏa mãn $2 ≤ i ≤ j ≤ n - 1$ sao cho:

$\sum_{k=1}^{i-1} v_k = \sum_{k=i}^{j} v_k = \sum_{k=j+1}^{n} v_k$

Dữ liệu vào

Dòng đầu tiên chứa số nguyên $n$ ($1 ≤ n ≤ 5 · 10^5$), đại diện cho số lượng phần tử trong dãy.

Dòng thứ hai chứa $n$ số nguyên $v_1, v_2, \ldots, v_n$ ($|v_i| \le 10^9$), là các phần tử của dãy $v$.

Kết quả

In ra một số nguyên duy nhất, là số cách chia dãy thành ba phần có tổng bằng nhau.

Chấm điểm

Subtask 1 (30 points). $n ≤ 2000$

Subtask 2 (70 points). $1 ≤ n ≤ 5 · 10^5$

Ví dụ

Input

6
1 0 1 0 1 0

Output

4

Ghi chú

Ở ví dụ trên, dãy có $6$ phần tử với $4$ cặp chỉ số thỏa mãn là $(i=2, j=3)$, $(i=2, j=4)$, $(i=3, j=3)$ và $(i=3, j=4)$.