Toudou có ~N~ cái bánh, mỗi cái bánh mang năng lượng ~W_i~. Có bao nhiêu cách chia đống bánh ra thành ~3~ phần liên tiếp sao cho mỗi chiếc bánh thuộc đúng một phần và tổng giá trị năng lượng của 3 phần là bằng nhau?

Nói cách khác, hãy đếm số cặp ~(i, j)~ sao cho ~2 ≤ i ≤ j ≤ n−1~ và:

$$\sum_{k=1}^{i-1}a_k=\sum_{k=i}^{j}a_k=\sum_{k=j+1}^{N}a_k$$

Input

• Dòng đầu tiên, gồm một số nguyên ~N~;
• Dòng tiếp theo, gồm ~N~ số nguyên ~W_i~ - là giá trị năng lượng của mỗi cái bánh.

Giới hạn:

• ~1 ≤ N ≤ 500000; |W_i| ≤ 10^9~. Trong đó ~30\%~ số test có ~1 ≤ N ≤ 5000~.

Output

• Gồm một dòng duy nhất là kết quả bài toán.

Sample

Input #1

5
1 2 3 0 3

Output #1

2

Input #2

4
0 1 -1 0

Output #2

1

Problem source: Kc97ble - Free Contest