Một hôm Merlin qua về tòa tháp của mình thì thấy tất cả ~n~ hũ rượu thuốc quý đều bị Morgana yểm bùa.

Merlin biết cách gỡ bỏ bùa chú, nhưng điều này đòi hỏi các bình cần khử bùa phải có rượu và chứa một lượng rượu như nhau.

Sau một lúc suy nghĩ Merlin quyết định chọn một số bình, rót hết rượu từ những bình được chọn sang các bình còn lại sao cho chúng có cùng một lượng rượu. Những bình rỗng không thể gỡ bỏ bùa chú bị đập vỡ. Với những bình còn lại Merlin tiến hành xử lý gỡ bỏ bùa chú. Bản thân các bình đựng rượu đều rất đẹp và quý, vì vậy Merlin có gắng chọn cách làm sao cho số bình phải đập bỏ là ít nhất.

Lưu ý: Lượng nước trong các bình còn lại có thể không nguyên.

Yêu cầu:

Hãy xác định số lượng bình tối thiểu phải đập bỏ.

Dữ liệu vào:

• Dòng đầu tiên chứa số nguyên ~n~ ~(2 \leq n \leq 10^5)~,
• Dòng thứ ~2~ chứa n số nguyên ~a_1, a_2, . . . ., a_n~ – số lượng rượu trong các bình ~(1 \leq a_i \leq 10^9)~.

Kết quả ra:

Một số nguyên – số lượng bình tối thiểu phải đập bỏ.

Sample Input

5
1 2 3 4 5

Sample Output

2

Nguồn: Kỹ thuật lập trình - Thầy Nguyễn Thanh Tùng.