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: interview

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)



# Made By Mostafa_Khaled

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)


n = int(input())
a = sorted(list(map(int, input().split())))

maxe = max(a)
cnt = []
cur = 1
k = 0
i = 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)