Cho một băng số gồm n số nguyên, mỗi số được viết trên một ô. Hãy cắt băng 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 đầu ghi n (n ≤ 1000)

• Dòng tiếp theo ghi n số nguyên a1, a2, ..., an (ai ≤ 1000)

Dữ liệu ra:

Ghi K là số đoạn cần chia.

Sample Input

8
10 2 6 2 5 2 1 2

Sample Output

3