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

Merlin biết cách gỡ bùa, nhưng chỉ làm được với những hũ còn rượu và có lượng rượu bằng nhau. Merlin quyết định chọn một số hũ để rót hết rượu từ các hũ đó sang các hũ còn lại sao cho các hũ còn lại có cùng một lượng rượu. Những hũ bị rót hết rượu sẽ trở thành rỗng và phải đập bỏ.

Vì các hũ rất quý, Merlin muốn số hũ phải đập bỏ là ít nhất.

Yêu cầu

Cho ~n~ hũ với lượng rượu ban đầu ~a_1, a_2, \dots, a_n~. Merlin chọn một tập hũ để rót hết rượu sang các hũ còn lại sao cho:

• Mọi hũ còn lại đều không rỗng và có cùng lượng rượu.
• Chỉ được rót rượu từ các hũ bị chọn sang các hũ còn lại (các hũ còn lại chỉ có thể tăng lượng rượu, không được đổ bớt đi).

Hãy xác định số hũ tối thiểu phải đập bỏ.

Dữ liệu

• Dòng 1: số nguyên ~n~ (~2 \le n \le 10^5~).
• Dòng 2: ~n~ số nguyên ~a_1, a_2, \dots, a_n~ — lượng rượu trong mỗi hũ (~1 \le a_i \le 10^9~).

Kết quả

Ghi ra một số nguyên — số hũ tối thiểu phải đập bỏ.

Ví dụ

Ví dụ 1

Input

5
1 2 3 4 5

Output

2

Giải thích

Ví dụ 1

Tổng lượng rượu là ~1+2+3+4+5 = 15~.

Nếu giữ lại ~3~ hũ có lượng ban đầu ~1,2,3~ (các hũ này không thể giảm rượu), và rót hết rượu từ 2 hũ còn lại (~4~ và ~5~) sang, ta có thể chia để cả 3 hũ đều đạt ~5~ (vì ~15/3 = 5~). Khi đó 2 hũ bị rót hết trở thành rỗng và phải đập bỏ.

Không thể giữ lại ~4~ hũ vì khi đó lượng cuối mỗi hũ sẽ là ~15/4 = 3.75~, nhưng chỉ có ~3~ hũ có ~a_i \le 3.75~.

Vậy số hũ tối thiểu phải đập bỏ là ~2~.

Ràng buộc và chấm điểm

Ràng buộc

• ~2 \le n \le 10^5~
• ~1 \le a_i \le 10^9~