| Codeforces Round 326 (Div. 1) |
|---|
| Закончено |
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 хода, потому что нет такого поднабора гирь, где гирь было бы больше одной, а сумма равнялась степени двойки.
