Xét dãy số nguyên ~a_1, a_2, ..., a_N~ ~(0 < N \le 10^6,\ |a_i| \le 10^6,\ 1 \le i \le N)~, một đoạn gồm các phần tử liên tiếp từ ~a_i~ đến ~a_j~ ~(1 \le i \le j \le N)~ của dãy số ~a_1, a_2, ..., a_N~ được gọi là dãy con liên tiếp. Ví dụ: dãy ~1, 4, 3~ là dãy con liên tiếp của dãy số ~0, 1, 4, 3, 5, 7~; dãy ~1, 3, 5~ không phải là dãy con liên tiếp của dãy số ~0, 1, 4, 3, 5, 7~.

Như vậy, mỗi dãy con liên tiếp được xác định bởi một cặp ~(i, j)~, dãy có ~1~ phần tử thì ~i = j~. Hai dãy con liên tiếp ~(i_1, j_1)~ và ~(i_2, j_2)~ được gọi là khác nhau nếu có ~i_1 \ne i_2~ hoặc ~j_1 \ne j_2~.

Cho dãy số nguyên ~a_1, a_2, ..., a_N~ ~(0 < N \le 10^6,\ |a_i| \le 10^6,\ 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ử của dãy bằng nhau. Chỉ đưa ra một kết quả là số lượng dãy lớn nhất (có cùng tổng các phần tử của dãy).

Dữ liệu đầu vào

Gồm hai dòng:

• Dòng đầu tiên gồm một số nguyên dương ~N~.
• Dòng thứ hai gồm ~N~ số nguyên ~a_1, a_2, ..., a_N~, các số cách nhau bằng dấu cách.

Dữ liệu đầu ra

Gồm một số nguyên là kết quả tìm được.

Ràng buộc dữ liệu

• Có 40% số test ứng với ~N \le 50~.
• Có 40% số test ứng với ~50 < N \le 10^3~.
• Có 20% số test ứng với ~10^3 \le N \le 10^6~.

BỘ TEST KHÔNG KIỂM TRA CHO SUBTASK CUỐI CÙNG

Ví dụ

Ví dụ 1

INPUT

5
1 1 2 1 3

OUTPUT

3

Giải thích:

• ~3~ dãy có cùng tổng là ~1~ (gồm ~1~ phần tử) là ~(1, 1), (2, 2), (4, 4)~.
• ~3~ dãy có cùng tổng là ~4~: ~(5, 5), (1, 3), (2, 4)~.
• ~2~ dãy có cùng tổng là ~5~: ~(4, 5), (1, 4)~.

Với tổng là ~1~ hoặc ~4~ thì có số dãy con nhiều nhất là ~3~.