Duff тренируется с гирями. Чтобы держать девушку в тонусе, Malek дал ей задание. Он дал ей последовательность гирь. Из них i-я весит 2wi фунтов. За каждый ход Duff может поднять некоторые из оставшихся гирь и выбросить их. Она так делает до тех пор, пока гири не закончатся. Malek попросил её минимизировать количество шагов.
Duff — поклонница спортивного программирования. Поэтому на каждом шагу она может поднять и отбросить последовательность гирь 2a1, ..., 2ak тогда и только тогда, когда существует неотрицательное целое число x, такое, что 2a1 + 2a2 + ... + 2ak = 2x, то есть, сумма весов гирь сама должна быть степенью двойки.
Duff — поклонница спортивного программирования, но не программист. Поэтому она попросила Вас о помощи. Помогите ей минимизировать количество шагов.
Выходные данные
Выведите минимальное количество шагов на единственной строке.
Примечание
В первом примере: один из оптимальных способов — выбросить первые три гири на первом ходу, а остальные — на втором ходу. Произвести эти действия за один ход невозможно, так как их сумма не является степенью двойки.
Во втором примере: единственный оптиальный способ — на каждом ходу выбрасывать по гире. Это нельзя сделать менее, чем за 4 хода, потому что нет такого поднабора гирь, где гирь было бы больше одной, а сумма равнялась степени двойки.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5
1 1 2 3 3
|
2
|
|
2
|
4
0 1 2 3
|
4
|