Nâng tạ

Duff có $N$ quả tạ. Quả tạ thứ $i$ có khối lượng đúng bằng $2^{w_i}$ pound.

Mỗi bước, Duff chọn một tập con khác rỗng gồm các quả tạ còn lại rồi vứt bỏ tất cả chúng. Tuy nhiên cô chỉ được phép vứt tập các quả tạ $2^{a_1},2^{a_2},\dots ,2^{a_k}$ nếu tổng khối lượng của chúng là một luỹ thừa của $2$, nghĩa là tồn tại số nguyên không âm $x$ sao cho:

$$2^{a_1}+2^{a_2}+\cdots +2^{a_k}=2^x$$

Duff lặp lại thao tác trên cho tới khi không còn quả tạ nào. Hãy tìm số bước ít nhất cần thực hiện.

Dữ liệu vào

• Dòng đầu tiên chứa số nguyên $N$ là số quả tạ.
• Dòng thứ hai chứa $N$ số nguyên $w_1,w_2,\dots ,w_N$ là số mũ của các quả tạ.

Dữ liệu ra

Một số nguyên duy nhất là số bước ít nhất.

Ràng buộc

• $1\le N\le {10}^6$
• $0\le w_i\le {10}^6$

Ví dụ