Cho một số nguyên dương \(n\) và một mảng \(A\) chứa \(n\) số nguyên (có thể âm). Bạn muốn cắt một nhát cắt trên mảng đó để chia mảng đó thành hai đoạn trái và phải, sao cho cả hai đoạn đều có ít nhất một phần tử và tổng các phần tử của hai đoạn bằng nhau.

Đề bài yêu cầu đếm có bao nhiêu cách cắt thỏa mãn điều kiện trên.

Input

• Dòng đầu tiên chứa một số nguyên dương \(n\) \((1 \leq n \leq 2*10^5)\)
• Dòng thứ hai chứa \(n\) số nguyên \(A_i,\) là số thứ \(i\) của mảng \(A (|A_i| \leq 10^9)\)

Output

• Số cách cắt mảng \(A\) cho trước, sao cho tổng của phân đoạn trái và phân đoạn phải sau khi cắt có tổng các phần tử bằng nhau.

Example

4
1 2 2 1

1

6
1 1 1 3 -3 3

2