Cho một dãy số gồm \(N\) số nguyên \(A_1, A_2, ...A_N\).

Yêu cầu: 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à \(A_i (0 <= A_i <= 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