Chia ba phần bằng nhau

Cho dãy số nguyên \(a_1, a_2, \dots, a_n\). Hãy đếm số cách chọn hai vị trí cắt \(i, j\) (\(1 \le i < j < n\)) để chia dãy thành ba đoạn liên tiếp, khác rỗng:

sao cho tổng ba đoạn bằng nhau.

Input

• Dòng đầu tiên chứa số nguyên dương \(n\) (\(1 \le n \le 2 \cdot 10^5\)).
• Dòng thứ hai chứa \(n\) số nguyên \(a_1, a_2, \dots, a_n\) (\(|a_i| \le 10^9\)).

Output

• Một số nguyên là số cách chia.

Subtask

• \(30\%\) số test: \(n \le 300\).
• \(30\%\) số test: \(n \le 5000\).
• \(40\%\) số test: không có ràng buộc gì thêm.

Sample Input 1

5
1 2 3 0 3

Sample Output 1

2

Sample Input 2

4
0 1 -1 0

Sample Output 2

1

Notes

Ở ví dụ 1, hai cách chia là \([1, 2]\,|\,[3]\,|\,[0, 3]\) và \([1, 2]\,|\,[3, 0]\,|\,[3]\), mỗi phần đều có tổng bằng \(3\).