Dãy tổng

Cho dãy \(A\) gồm \(n\) phần tử.

Yêu cầu: Hãy chia dãy \(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ử trong mỗi đoạn đều bằng nhau. Mỗi phần tử thuộc đúng một đoạn.

Input

• Dòng đầu chứa số nguyên \(n\) (\(1 \le n \le 1000\)).
• Dòng thứ hai chứa \(n\) phần tử của dãy \(A\) (\(0 \le A_i \le 10^9\)).

Output

In ra số đoạn con tối đa có thể chia được.