Po là người yêu thích màu sắc. Trong ngày sinh nhật của mình Po được các bạn tặng một món quà gồm ~n~ hộp màu, hộp thứ ~i~ được thể hiện bằng màu ~a_i~. Po muốn màu sắc trong tất cả các hộp khác nhau nên đã thực hiện thao tác trộn màu. Mỗi thao tác chọn hai màu có giá trị ~x~ và ~y~ khác nhau để trộn, sau khi trộn thì màu ~x~ vẫn giữ nguyên, còn màu ~y~ sẽ trở thành màu ~x+y~.

Yêu cầu: Hãy cho biết Po cần thực hiện ít nhất bao nhiêu thao tác trộn màu để được ~n~ màu khác nhau?

Dữ liệu vào

• Dòng đầu tiên ghi số nguyên dương ~n~ ~(1≤n≤10^5)~;
• Dòng thứ hai ghi lần lượt các số ~a_1,a_2,…,a_n~ ~(1≤a_i≤10^9)~;

Kết quả

• Một số nguyên duy nhất cho biết số thao tác ít nhất cần thực hiện.

Ví dụ:

Input

4
1 2 3 2 

Output

1