Cho một dãy số gồm N số nguyên A1, A2, ...AN. Hãy tìm cách chia dãy số này thành nhiều đoạn nhất sao cho tổng các phần tử trong các đoạn là bằng nhau.

Dữ liệu vào:

• Dòng 1 : gồm 1 số nguyên N (1 <= N <= 1000)

• Dòng 2 : gồm N số, số thứ i là Ai (0 <= Ai <= 1000000) , các số cách nhau bởi khoảng trắng

Dữ liệu ra:

Một số duy nhất là số đoạn cần chia.

Sample Input

8
12 6 4 2 1 5 4 2

Sample Output

3