Recently, Duff has been practicing weight lifting. As a hard practice, Malek gave her a task. He gave her a sequence of weights. Weight of i-th of them is 2^{w}_{i} pounds. In each step, Duff can lift some of the remaining weights and throw them away. She does this until there's no more weight left. Malek asked her to minimize the number of steps. [Image] 

Duff is a competitive programming fan. That's why in each step, she can only lift and throw away a sequence of weights 2^{a}_1, ..., 2^{a}_{k} if and only if there exists a non-negative integer x such that 2^{a}_1 + 2^{a}_2 + ... + 2^{a}_{k} = 2^{x}, i. e. the sum of those numbers is a power of two.

Duff is a competitive programming fan, but not a programmer. That's why she asked for your help. Help her minimize the number of steps. 


-----Input-----

The first line of input contains integer n (1 ≤ n ≤ 10^6), the number of weights.

The second line contains n integers w_1, ..., w_{n} separated by spaces (0 ≤ w_{i} ≤ 10^6 for each 1 ≤ i ≤ n), the powers of two forming the weights values.


-----Output-----

Print the minimum number of steps in a single line.


-----Examples-----
Input
5
1 1 2 3 3

Output
2

Input
4
0 1 2 3

Output
4



-----Note-----

In the first sample case: One optimal way would be to throw away the first three in the first step and the rest in the second step. Also, it's not possible to do it in one step because their sum is not a power of two.

In the second sample case: The only optimal way is to throw away one weight in each step. It's not possible to do it in less than 4 steps because there's no subset of weights with more than one weight and sum equal to a power of two.

Difficulty: MEDIUM
Tags: Greedy algorithms
Skill types: Greedy algorithms

Starter code:

Solutions:
n = input()
a = [0] * 1000021
ans = 0
b = 0
for u in map(int, input().split()):
	a[u] += 1
for u in a:
	b += u
	if b & 1:
		ans += 1
	b >>= 1
print(ans)


n = int(input())
weights = list(map(int, input().split()))
counter = [0] * (10 ** 6 + 21)
for weight in weights:
	counter[weight] += 1
ans = 0
for i in range(10 ** 6 + 21):
	(weight, count) = (i, counter[i])
	if count > 0 and count // 2 > 0:
		counter[weight + 1] += count // 2
		count -= count // 2 * 2
	ans += count
print(ans)


def main():
	input()
	l = [0] * 1000001
	for w in map(int, input().split()):
		l[w] += 1
	t = rest = 0
	for x in l:
		t += x
		if t & 1:
			rest += 1
		t >>= 1
	print(bin(t).count('1') + rest)
main()


n = int(input())
MAXN = 10 ** 6 + 20
bit = [0] * MAXN
for s in input().split(' '):
	ss = int(s)
	bit[ss] += 1
	while bit[ss] > 1:
		bit[ss + 1] += 1
		bit[ss] = bit[ss] & 1
		ss += 1
print(sum(bit))


n = int(input())
l = [0] * (10 ** 6 + 100)
for i in map(int, input().split()):
	l[i] += 1
cur = ans = 0
for i in l:
	cur += i
	if cur % 2:
		ans += 1
	cur //= 2
print(ans)


def ok(x):
	if x == 0:
		return False
	return x & x - 1
n = int(input())
arr = list(map(int, input().split()))
f = [0] * 2000020
for i in arr:
	f[i] += 1
ans = 0
for i in range(2000010):
	if f[i] % 2 == 1:
		ans += 1
		f[i] -= 1
	f[i + 1] += f[i] // 2
print(ans)


n = int(input())
w = map(int, input().split(' '))
N = 1000001
s = [0] * N
for i in w:
	s[i] += 1
ans = 0
Z = 0
for i in range(0, N):
	Sum = s[i] + Z
	Z = Sum // 2
	ans += Sum % 2
while Z > 0:
	ans += Z % 2
	Z //= 2
print(ans)


from collections import *
import sys
import math
from functools import reduce

def factors(n):
	return set(reduce(list.__add__, ([i, n // i] for i in range(1, int(n ** 0.5) + 1) if n % i == 0)))

def li():
	return [int(i) for i in input().rstrip('\n').split(' ')]

def st():
	return input().rstrip('\n')

def val():
	return int(input())

def stli():
	return [int(i) for i in input().rstrip('\n')]

def persquare(x):
	return 1 if x ** 0.5 == int(x ** 0.5) else 0
n = val()
l = sorted(li())
currlist = [0 for i in range(10 ** 6 + 22)]
for i in l:
	currlist[i] += 1
tot = 0
for i in range(10 ** 6 + 21):
	while currlist[i] > 1:
		temp = 2 ** int(math.log2(currlist[i]))
		currlist[i] -= temp
		currlist[i + 1] += temp // 2
print(sum(currlist))


def main():
	n = int(input())
	w = list(map(int, input().split()))
	bits = [0] * (10 ** 6 + 100)
	for e in w:
		bits[e] += 1
	(cur, res) = (0, 0)
	for e in bits:
		cur += e
		if cur % 2:
			res += 1
		cur //= 2
	print(res)
main()


import math
n = int(input())
w = [int(i) for i in input().split()]
mxN = 1000000 + math.ceil(math.log2(1000000)) + 1
btStr = [0] * mxN
for i in w:
	btStr[i] += 1
steps = 0
for i in range(mxN - 1):
	btStr[i + 1] += btStr[i] // 2
	btStr[i] = btStr[i] % 2
	steps += btStr[i]
print(steps)


n = int(input())
a = [0 for i in range(10 ** 6 + 1)]
for x in input().split():
	a[int(x)] += 1
c = 0
prev = 0
for el in a:
	prev += el
	if prev % 2 == 1:
		c += 1
	prev //= 2
while prev > 0:
	c += prev % 2
	prev //= 2
print(c)


import sys
input = sys.stdin.readline
print = sys.stdout.write
n = int(input())
two = [0] * (10 ** 6 + 100)
for i in map(int, input().split()):
	two[i] += 1
res = 0
for i in range(10 ** 6 + 99):
	two[i + 1] += two[i] // 2
	two[i] %= 2
	res += two[i]
print(str(res))


n = input()
weights = input()
bits = [0 for i in range(1001015)]
for w in weights.split():
	bits[int(w)] += 1
ans = 0
for i in range(1001010):
	bits[i + 1] += bits[i] >> 1
	ans += bits[i] & 1
print(ans)


N = int(1000000.0) + 20
n = int(input())
m = [0] * N
k = 1000000.0 + 1
for x in map(int, input().split()):
	m[x] += 1
	k = min(k, x)
result = 0
while k < N - 1:
	v = m[k]
	m[k + 1] += v >> 1
	result += v & 1
	k += 1
print(result + m[-1])


n = int(input())
num = [0] * (2 * 10 ** 6 + 1)
for i in map(int, input().split()):
	num[i] += 1
ans = 0
for i in range(2 * 10 ** 6):
	num[i + 1] += num[i] // 2
	ans += num[i] % 2
print(ans + num[-1] % 2)


n = int(input())
l = list(map(int, input().split()))
cnt = [0] * (10 ** 6 + 100)
for i in l:
	cnt[i] += 1
s = 0
ans = 0
for i in cnt:
	s += i
	ans += s % 2
	s //= 2
print(ans)


from sys import maxsize, stdout, stdin, stderr
mod = int(1000000000.0 + 7)
import sys

def I():
	return int(stdin.readline())

def lint():
	return [int(x) for x in stdin.readline().split()]

def S():
	return list(map(str, input().strip()))

def grid(r, c):
	return [lint() for i in range(r)]
from collections import defaultdict, Counter, deque
import math
import heapq
from heapq import heappop, heappush
import bisect
from itertools import groupby
from itertools import permutations as comb

def gcd(a, b):
	while b:
		a %= b
		tmp = a
		a = b
		b = tmp
	return a

def lcm(a, b):
	return a // gcd(a, b) * b

def check_prime(n):
	for i in range(2, int(n ** (1 / 2)) + 1):
		if not n % i:
			return False
	return True

def nCr(n, r):
	return fact(n) // (fact(r) * fact(n - r))

def fact(n):
	res = 1
	for i in range(2, n + 1):
		res = res * i
	return res

def primefactors(n):
	num = 0
	while n % 2 == 0:
		num += 1
		n = n / 2
	for i in range(3, int(math.sqrt(n)) + 1, 2):
		while n % i == 0:
			num += 1
			n = n // i
	if n > 2:
		num += 1
	return num

def ask(a):
	print('? {}'.format(a), flush=True)
	n = I()
	return n

def dfs(i, p):
	(a, tmp) = (0, 0)
	for j in d[i]:
		if j != p:
			a += 1
			tmp += dfs(j, i)
	if a == 0:
		return 0
	return tmp / a + 1

def primeFactors(n):
	l = []
	while n % 2 == 0:
		l.append(2)
		n = n // 2
	if n > 2:
		l.append(n)
	return l
n = I()
s = lint()
tmp = 100 + max(s)
d = [0] * tmp
for i in range(n):
	d[s[i]] += 1
cnt = 0
for i in range(tmp):
	if d[i] > 0:
		d[i + 1] += d[i] // 2
		d[i] %= 2
		cnt += d[i]
print(cnt)


N = int(1000000.0 + 100)
n = int(input())
arr = list(map(int, input().split()))
cnt = [0] * N
for i in arr:
	cnt[i] += 1
(res, s) = (0, 0)
for i in range(N):
	s += cnt[i]
	res += s % 2
	s //= 2
print(res)


def main():
	input()
	l = [0] * 1000020
	for w in map(int, input().split()):
		l[w] += 1
	for (w, x) in enumerate(l):
		if x:
			l[w] = x & 1
			while x:
				x >>= 1
				w += 1
				if x & 1:
					l[w] += 1
	print(sum(l))

def __starting_point():
	main()
__starting_point()


a = int(input())
w = map(int, input().split(' '))
m = [0] * 1000001
for i in w:
	m[i] += 1
res = 0
pre = 0
for i in range(0, 1000001):
	s = m[i] + pre
	res += s % 2
	pre = s // 2
while pre > 0:
	res += pre % 2
	pre = pre // 2
print(res)


n = int(input())
a = list(map(int, input().split()))
di = [0] * (10 ** 6 + 699)
for i in a:
	di[i] += 1
ans = 0
for i in range(10 ** 6 + 698):
	(di[i], di[i + 1]) = (di[i] % 2, di[i + 1] + di[i] // 2)
	if di[i] % 2 == 1:
		ans += 1
print(ans)


n = int(input())
A = list(map(int, input().split()))
d = {}
for i in range(n):
	if A[i] in d:
		k = A[i]
		while k in d:
			del d[k]
			k += 1
		d[k] = 1
	else:
		d[A[i]] = 1
print(len(d))


def inc(a, w):
	n = len(a)
	i = w
	while i < n and a[i] == 1:
		a[i] = 0
		i += 1
	if i < n:
		a[i] = 1
	else:
		a.append(1)
n = int(input())
x = input().split(' ')
w = [int(y) for y in x]
a = [0] * 1000024
for t in w:
	inc(a, t)
print(sum(a))


n = int(input())
l = list(map(int, input().split()))
bit = [0] * (10 ** 6 + 101)
for i in l:
	bit[i] = bit[i] + 1
ans = 0
s = 0
for i in bit:
	s = s + i
	ans = ans + s % 2
	s = s // 2
print(ans)


from collections import Counter, defaultdict, deque
import heapq as hq
import math
import sys
input = sys.stdin.readline

def solve():
	n = int(input())
	c = [0] * (10 ** 6 + 1000)
	for el in (int(x) for x in input().split()):
		c[el] += 1
	res = 0
	for i in range(10 ** 6 + 999):
		c[i + 1] += c[i] // 2
		res += c[i] % 2
	print(res)
tt = 1
for test in range(tt):
	solve()


from sys import stdin
stdin.readline()
a = [0] * 1000021
ans = b = 0
for u in map(int, stdin.readline().split()):
	a[u] += 1
for u in a:
	b += u
	ans += b & 1
	b >>= 1
print(ans)


l = [0] * 1100001
input()
for i in map(int, input().split()):
	l[i] += 1
for i in range(1100000):
	(l[i], l[i + 1]) = (l[i] % 2, l[i + 1] + l[i] // 2)
print(sum(l))


n = int(input())
a = [int(x) for x in input().split()]
l = [0] * (10 ** 6 + 100)
for x in a:
	l[x] += 1
cur = 0
ans = 0
for x in l:
	cur += x
	if cur % 2:
		ans += 1
	cur //= 2
print(ans)


import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

def prime_factors(x):
	s = set()
	n = x
	i = 2
	while i * i <= n:
		if n % i == 0:
			while n % i == 0:
				n //= i
			s.add(i)
		i += 1
	if n > 1:
		s.add(n)
	return s
from collections import Counter
import heapq
import math
from collections import Counter
from bisect import bisect_right
import heapq
import sys
input = sys.stdin.buffer.readline

def add(x):
	global ans
	if x >= 1 and x <= n and (arr[x] > arr[x - 1]) and (arr[x] > arr[x + 1]):
		ans += arr[x]
	elif x >= 1 and x <= n and (arr[x] < arr[x - 1]) and (arr[x] < arr[x + 1]):
		ans -= arr[x]

def erase(x):
	global ans
	if x >= 1 and x <= n and (arr[x] > arr[x - 1]) and (arr[x] > arr[x + 1]):
		ans -= arr[x]
	elif x >= 1 and x <= n and (arr[x] < arr[x - 1]) and (arr[x] < arr[x + 1]):
		ans += arr[x]
n = int(input())
import math
arr = list(map(int, input().split()))
bit = [0] * (10 ** 6 + 100)
for i in arr:
	bit[i] += 1
ans = 0
for i in range(len(bit) - 1):
	bit[i + 1] += bit[i] // 2
	bit[i] = bit[i] % 2
print(sum(bit))


n = int(input())
lis = list(map(int, input().split()))
has = [0] * 1000500
ans = 0
for i in lis:
	has[i] += 1
for i in range(1000499):
	has[i + 1] += has[i] // 2
	if has[i] % 2 != 0:
		ans += 1
print(ans)


n = int(input())
w = map(int, input().split())
m = 1000001
s = [0] * m
for i in w:
	s[i] += 1
ans = 0
z = 0
for i in range(m):
	n_s = s[i] + z
	z = n_s // 2
	ans += n_s % 2
while z > 0:
	ans += z % 2
	z //= 2
print(ans)


from collections import defaultdict
mxn = 10 ** 6
n = int(input())
a = list(map(int, input().split()))
d = [0] * (mxn + 2)
for i in a:
	d[i] += 1
for i in range(1 + mxn):
	q = d[i] // 2
	d[i + 1] += q
	d[i] -= 2 * q
ct = 0
for i in d:
	ct += bin(i).count('1')
print(ct)


import sys
readline = sys.stdin.readline
N = int(readline())
A = list(map(int, readline().split()))
K = 100 + max(A)
L = [0] * K
for a in A:
	L[a] += 1
for i in range(K):
	if L[i] > 1:
		L[i + 1] += L[i] // 2
		L[i] = L[i] % 2
print(sum(L))


n = input()
w = list(map(int, input().split()))
a = [0] * 1000021
ans = 0
for u in w:
	a[u] += 1
for i in range(1000020):
	t = a[i]
	if t:
		a[i + 1] += t >> 1
		ans += t & 1
print(ans)


n = int(input())
lis = sorted(map(int, input().split()))
ans = c = 0
c = 1
for i in range(1, n):
	if lis[i] == lis[i - 1]:
		c += 1
	else:
		while lis[i] != lis[i - 1] and c > 0:
			if c % 2:
				ans += 1
			c = c // 2
			lis[i - 1] += 1
		c += 1
while c > 0:
	if c % 2:
		ans += 1
	c = c // 2
print(ans)


n = int(input())
list = map(int, input().split())
N = [0] * 1000001
for i in list:
	N[i] += 1
ans = 0
temp = 0
for j in range(1000001):
	number = N[j] + temp
	temp = number // 2
	ans += number % 2
while temp > 0:
	ans += temp % 2
	temp //= 2
print(ans)