It can be shown that any positive integer x can be uniquely represented as x = 1 + 2 + 4 + ... + 2^{k} - 1 + r, where k and r are integers, k ≥ 0, 0 < r ≤ 2^{k}. Let's call that representation prairie partition of x.

For example, the prairie partitions of 12, 17, 7 and 1 are:  12 = 1 + 2 + 4 + 5,

17 = 1 + 2 + 4 + 8 + 2,

7 = 1 + 2 + 4,

1 = 1. 

Alice took a sequence of positive integers (possibly with repeating elements), replaced every element with the sequence of summands in its prairie partition, arranged the resulting numbers in non-decreasing order and gave them to Borys. Now Borys wonders how many elements Alice's original sequence could contain. Find all possible options!


-----Input-----

The first line contains a single integer n (1 ≤ n ≤ 10^5) — the number of numbers given from Alice to Borys.

The second line contains n integers a_1, a_2, ..., a_{n} (1 ≤ a_{i} ≤ 10^12; a_1 ≤ a_2 ≤ ... ≤ a_{n}) — the numbers given from Alice to Borys.


-----Output-----

Output, in increasing order, all possible values of m such that there exists a sequence of positive integers of length m such that if you replace every element with the summands in its prairie partition and arrange the resulting numbers in non-decreasing order, you will get the sequence given in the input.

If there are no such values of m, output a single integer -1.


-----Examples-----
Input
8
1 1 2 2 3 4 5 8

Output
2 

Input
6
1 1 1 2 2 2

Output
2 3 

Input
5
1 2 4 4 4

Output
-1



-----Note-----

In the first example, Alice could get the input sequence from [6, 20] as the original sequence.

In the second example, Alice's original sequence could be either [4, 5] or [3, 3, 3].

Difficulty: HARD
Tags: Sorting

Constructive algorithms

Mathematics

Greedy algorithms
Skill types: Sorting

Greedy algorithms

Starter code:

Solutions:
n = int(input())
a = sorted(list(map(int, input().split())))
maxe = max(a)
cnt = []
(cur, k, i) = (1, 0, 0)
while i < n:
	cnt.append(0)
	while i < n and a[i] < cur:
		cnt[2 * k] += 1
		i += 1
	cnt.append(0)
	while i < n and a[i] == cur:
		cnt[2 * k + 1] += 1
		i += 1
	k += 1
	cur *= 2
cnt.append(0)
cnt.append(0)
maxe = len(cnt) - 1
maxk = cnt[1]
was = False
for l in range(maxk):
	cur = 1
	while cnt[cur] > 0:
		cnt[cur] -= 1
		cur += 2
	cnt[cur] -= 1
	cursum = 0
	ok = True
	for t in range(maxe, 0, -1):
		cursum += cnt[t]
		if cursum > 0:
			ok = False
			break
	if ok:
		print(l + 1, end=' ')
		was = True
if not was:
	print(-1)


from collections import Counter
from math import log2
powers = [2 ** p for p in range(64)]

def can():
	near = Counter()
	for num in set(nums):
		p = int(log2(num))
		near[p] += nums[num]
	seq_cp = seqs - Counter()
	for num in set(near):
		cnt = near[num]
		while cnt != 0 and num < 64:
			dif = min(cnt, seq_cp[powers[num]])
			cnt -= dif
			seq_cp[powers[num]] -= dif
			num += 1
		if cnt > 0:
			return False
	return True
n = int(input())
seq = list(map(int, input().split()))
cnt = Counter(seq)
nums = Counter(seq)
seqs = Counter()
cur_cnt = cnt[1]
cur_pow = 1
while cur_cnt != 0:
	nums[cur_pow] -= cur_cnt
	cur_pow *= 2
	if cur_cnt > cnt[cur_pow]:
		seqs[cur_pow // 2] = cur_cnt - cnt[cur_pow]
		cur_cnt = cnt[cur_pow]
for num in set(nums):
	addition = nums[num]
	nums[num] = 0
	nums[2 ** int(log2(num))] += addition
nums -= Counter()
seqs -= Counter()
cur_len = sum((seqs[num] for num in set(seqs)))
res = []
cur_pow = 1
while can():
	res.append(cur_len)
	while seqs[cur_pow] == 0 and cur_pow <= 2 ** 63:
		cur_pow *= 2
	if cur_pow > 2 ** 63:
		break
	other_pow = 1
	while other_pow <= cur_pow:
		nums[other_pow] += 1
		other_pow *= 2
	seqs[cur_pow] -= 1
	cur_len -= 1
print(-1 if len(res) == 0 else ' '.join(map(str, reversed(res))))


from collections import Counter
n = int(input())
a = list(map(int, input().split()))

def get(cnt):
	c = Counter(a)
	last = []
	while c[1] and (cnt is None or len(last) < cnt):
		x = 1
		while c[x]:
			c[x] -= 1
			x *= 2
		last.append(x >> 1)
	rem = sorted(c.elements())
	i = 0
	for x in last[::-1]:
		if i < len(rem) and rem[i] < 2 * x:
			i += 1
	return len(last) if i == len(rem) else 0
mx = get(None)
(lo, hi) = (0, mx)
while lo < hi:
	mid = lo + hi >> 1
	if get(mid):
		hi = mid
	else:
		lo = mid + 1
if mx:
	print(*list(range(lo, mx + 1)))
else:
	print(-1)


from collections import Counter
from math import log2, ceil
MAX = ceil(log2(10 ** 12))

def can():
	seqs_cp = Counter(seqs)
	for num in set(nums):
		cnt = nums[num]
		while cnt != 0 and num < 2 ** 63:
			dif = min(cnt, seqs_cp[num])
			cnt -= dif
			seqs_cp[num] -= dif
			num *= 2
		if cnt > 0:
			return False
	return True
n = int(input())
seq = list(map(int, input().split()))
cnt = Counter(seq)
nums = Counter(seq)
seqs = Counter()
cur_cnt = cnt[1]
cur_pow = 1
while cur_cnt != 0:
	nums[cur_pow] -= cur_cnt
	cur_pow *= 2
	if cur_cnt > cnt[cur_pow]:
		seqs[cur_pow // 2] = cur_cnt - cnt[cur_pow]
		cur_cnt = cnt[cur_pow]
for num in set(nums):
	addition = nums[num]
	nums[num] = 0
	nums[2 ** int(log2(num))] += addition
nums -= Counter()
seqs -= Counter()
cur_len = sum((seqs[num] for num in set(seqs)))
res = []
cur_pow = 1
while can():
	res.append(cur_len)
	while seqs[cur_pow] == 0 and cur_pow <= 2 ** 63:
		cur_pow *= 2
	if cur_pow > 2 ** 63:
		break
	other_pow = 1
	while other_pow <= cur_pow:
		nums[other_pow] += 1
		other_pow *= 2
	seqs[cur_pow] -= 1
	cur_len -= 1
print(-1 if len(res) == 0 else ' '.join(map(str, reversed(res))))