Cho mảng A có N số nguyên, hãy chia A thành nhiều đoạn con liên tiếp nhất có thể sao cho tổng các phần tử trên mỗi đoạn này đều bằng nhau.

Input:

• Dòng 1. Ghi số nguyên dương N
• Dòng 2. Ghi N số nguyên ~A_1, A_2….A_N~

Output:

• Dòng 1. Ghi số nguyên dương K là kết quả bài toán.

Example:

Input:

6
1 2 3 3 2 1

Output:

4

Constraint:

~1<n\le10000~; ~0\le Ai \le 32000~;</p>