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.

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

Input

• Dòng đầu ghi số nguyên ~n~ (~2 \le n \le 10^5~).
• Dòng thứ hai ghi ~n~ số nguyên ~a_1, a_2, \dots, a_n~ là số lượng rượu trong các bình (~1 \le a_i \le 10^9~, ~i = 1 \dots n~).

Output

• In ra số lượng bình tối thiểu bị đập bỏ.

Sample Input 1

5
1 2 3 4 5

Sample Output 1

2