Cho một dãy gồm \(N\) số tự nhiên \(a_1, a_2, a_3...a_n\) \((1 \le N \le 10^6; |a_i| \le 10^9; 1 \le i \le N)\).

Yêu cầu: Đếm số lượng dãy con liên tiếp khác nhau mà có tổng các phần tử là bằng nhau. Chỉ đưa ra một kết quả là số lượng dãy con lớn nhất.

Dữ liệu vào:

• Dòng 1: Một số tự nhiên \(N\)
• Dòng 2: \(N\) số tự nhiên \(a_1, a_2, a_3...a_n\)

Dữ liệu ra:

• Một số nguyên duy nhất là kết quả tìm được.

Ràng buộc:

• Có 40% số test tương ứng 40% số điểm \(0 \le N \le 10^2\)
• Có 40% số test tương ứng 40% số điểm \(10^2 \le N \le 10^3\)
• Có 20% số test tương ứng 20% số điểm \(10^3 \le N \le 10^6\)

Input

5
1 1 2 1 4

Output

3

Giải thích

Có 3 dãy có cùng tổng 4: (5 đến 5), (1 đến 3), (2 đến 4)