Ba phần

Trong một buổi tổng kết, ban tổ chức có một dãy số nguyên \(A\) gồm \(N\) phần tử.
Họ muốn chọn hai chỉ số \(i, j\) sao cho \(1 \le i < j < N\) để chia dãy thành \(3\) đoạn liên tiếp:

• Đoạn \(1\): từ vị trí \(1\) đến \(i\),
• Đoạn \(2\): từ vị trí \(i+1\) đến \(j\),
• Đoạn \(3\): từ vị trí \(j+1\) đến \(N\),

và tổng các phần tử của mỗi đoạn bằng nhau.

Hãy đếm số cặp \((i, j)\) thỏa mãn yêu cầu trên.

Input

• Dòng đầu chứa số nguyên \(N\).
• Dòng thứ hai chứa \(N\) số nguyên \(A_1, A_2, \ldots, A_N\).

Output

In ra một số nguyên duy nhất là số cặp \((i, j)\) thỏa mãn.

Giới hạn

• \(3 \le N \le 10^5\)
• \(|A_i| \le 10^9\)

Scoring

• Subtask 1 (30%): \(3 \le N \le 200\)
• Subtask 2 (30%): \(3 \le N \le 2000\)
• Subtask 3 (40%): \(3 \le N \le 10^5\)

Input

5
1 2 3 0 3

Output

2