Trong một đợt ngoại khóa môn toán, thầy giáo tổ chức một trò chơi cho học sinh như sau: Chia học sinh thành các nhóm chơi, mỗi nhóm thầy đều phát cho một băng số giống nhau. Băng số là một dãy gồm N ô liên tiếp nhau, mỗi ô chứa một số tự nhiên. 

Yêu cầu: Cắt băng số thành nhiều đoạn sao cho tổng các số trong mỗi đoạn đều bằng nhau (mỗi đoạn gồm 1 hoặc nhiều ô liên tiếp nhau của băng số). Số đoạn cắt ra được cũng chính là số điểm thưởng cho mỗi đội. Trường hợp không thể cắt thành ít nhất 2 đoạn thỏa mãn yêu cầu thì số đoạn cắt được xem là bằng 1. Tất nhiên, mỗi đội chơi sẽ tìm cách cắt ra càng nhiều đoạn càng tốt. Là thành viên của đội chơi, em hãy lập trình để tìm được số đoạn cắt nhiều nhất.

Dữ liệu vào: Đọc từ file văn bản BS.INP có cấu trúc như sau:

- Dòng đầu tiên ghi một số nguyên dương N (1<N< 50000) là số ô của băng số.

- Dòng tiếp theo ghi N số nguyên dương A_i (A_i<10⁶) của băng số, mỗi số cách nhau một dấu cách.

Dữ liệu ra: Ghi ra file văn bản BS.OUT số nguyên K là số đoạn cắt nhiều nhất thỏa mãn yêu cầu trên.

Ví dụ: