Cho dãy \(N\) số nguyên dương \(a_i\). Đếm số cách chia dãy đã cho thành các đoạn liên tiếp sao cho tổng các phần tử mỗi đoạn từ đoạn thứ hai trở đi thì bằng nhau.

Input

• Dòng đầu tiên chứa \(N\) (\(1 \le N \leq 2 \cdot 10^5\))
• Dòng thứ hai chứa \(N\) số \(a_i\) (\(1 \le a_i \le 4\cdot 10^5, a_1 + a_2 + ... + a_N \le 4\cdot 10^5\))

Output

• Đưa ra số cách chia.

Example

5
1 1 2 1 1

6