A. Duff и гири
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Duff тренируется с гирями. Чтобы держать девушку в тонусе, Malek дал ей задание. Он дал ей последовательность гирь. Из них i-я весит 2wi фунтов. За каждый ход Duff может поднять некоторые из оставшихся гирь и выбросить их. Она так делает до тех пор, пока гири не закончатся. Malek попросил её минимизировать количество шагов.

Duff — поклонница спортивного программирования. Поэтому на каждом шагу она может поднять и отбросить последовательность гирь 2a1, ..., 2ak тогда и только тогда, когда существует неотрицательное целое число x, такое, что 2a1 + 2a2 + ... + 2ak = 2x, то есть, сумма весов гирь сама должна быть степенью двойки.

Duff — поклонница спортивного программирования, но не программист. Поэтому она попросила Вас о помощи. Помогите ей минимизировать количество шагов.

Входные данные

В первой строке ввода записано целое число n (1 ≤ n ≤ 106), количество гирь.

Во второй строке записано n целых чисел w1, ..., wn, разделенных пробелами (0 ≤ wi ≤ 106 для каждого 1 ≤ i ≤ n), — показатели весов гирь.

Выходные данные

Выведите минимальное количество шагов на единственной строке.

Примеры
Входные данные
5
1 1 2 3 3
Выходные данные
2
Входные данные
4
0 1 2 3
Выходные данные
4
Примечание

В первом примере: один из оптимальных способов — выбросить первые три гири на первом ходу, а остальные — на втором ходу. Произвести эти действия за один ход невозможно, так как их сумма не является степенью двойки.

Во втором примере: единственный оптиальный способ — на каждом ходу выбрасывать по гире. Это нельзя сделать менее, чем за 4 хода, потому что нет такого поднабора гирь, где гирь было бы больше одной, а сумма равнялась степени двойки.