773_C. Prairie Partition_9713
It can be shown that any positive integer x can be uniquely represented as x = 1 + 2 + 4 + ... + 2k - 1 + r, where k and r are integers, k ≥ 0, 0 < r ≤ 2k. 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 ≤ 105) — the number of numbers given from Alice to Borys.

The second line contains n integers a1, a2, ..., an (1 ≤ ai ≤ 1012; a1 ≤ a2 ≤ ... ≤ an) — 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].
#include <bits/stdc++.h>
using namespace std;
int n, num[101];
long long a;
int check(long long mid) {
  int mmin = mid, ret = num[0] - mid;
  for (int i = 1; i < 101; ++i) {
    ret = max(ret, 0);
    if (i & 1)
      ret += num[i];
    else {
      ret += (num[i] - mmin);
      mmin = min(mmin, num[i]);
    }
  }
  return !ret;
}
inline int id(long long x) {
  int ret = 0;
  while ((1LL << ret) < x) ++ret;
  if ((1LL << ret) == x) return ret << 1;
  return (ret << 1) - 1;
}
int main() {
  scanf("%d", &n);
  for (int i = 0; i < n; ++i) {
    scanf("%I64d", &a);
    ++num[id(a)];
  }
  int left = 1, right = num[0], res = -1;
  while (left <= right) {
    int mid = (left + right) >> 1;
    if (check(mid)) {
      res = mid;
      right = mid - 1;
    } else
      left = mid + 1;
  }
  if (res == -1)
    puts("-1");
  else
    for (int i = res; i <= num[0]; ++i)
      printf("%d%c", i, i == num[0] ? '\n' : ' ');
  return 0;
}

6
1 1 1 2 2 2
 8
1 1 2 2 3 4 5 8
 5
1 2 4 4 4
 2
1 2
 100
1 1 1 1 1 1 1 2 2 2 2 2 2 2 4 4 4 4 4 4 4 6 8 8 8 8 8 8 8 10 16 16 16 16 16 16 16 17 22 24 24 30 32 32 32 32 32 32 48 62 64 64 65 65 67 70 74 88 89 98 99 101 101 109 121 127 128 128 137 143 152 153 155 156 160 161 170 183 186 196 196 214 220 226 228 230 238 240 241 245 249 249 250 253 254 256 256 512 1024 1703
 2
1 1
 2
1 1000000000000
 25
1 1 1 1 2 2 2 2 4 4 4 4 8 8 8 8 13 15 16 16 31 32 36 41 55
 1
2
 1
1
 101
1 1 1 1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 2 2 2 2 4 4 4 4 4 4 4 4 4 4 4 4 5 8 8 8 8 8 8 8 8 8 8 8 8 16 16 16 16 16 16 16 16 16 16 16 16 26 32 32 32 32 32 32 32 32 49 58 64 64 64 64 64 64 122 128 128 128 128 128 128 256 256 256 256 256 491 512 512 512 512 718 1024 1024 1024 2935 3123
 45
1 1 1 1 1 2 2 2 2 2 2 2 4 4 4 4 4 4 8 8 8 8 8 8 16 16 16 16 16 32 32 32 32 32 41 64 64 64 64 128 128 128 256 256 512
 20
1 1 1 1 2 2 2 2 4 4 4 4 8 8 8 8 8 10 10 11
 101
1 1 1 1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 2 2 2 2 4 4 4 4 4 4 4 4 4 4 4 4 7 8 8 8 8 8 8 8 8 8 8 8 16 16 16 16 16 16 16 16 16 16 16 32 32 32 32 32 32 32 32 32 32 64 64 64 64 64 64 64 64 64 128 128 128 128 128 128 128 128 239 256 256 256 256 256 373 512 512 512 512 695 1024 1024 1024
 96
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 8 8 8 8 8 8 8 8 8 8 8 9 12 12 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 18 21
 40
1 2 4 8 16 32 64 128 256 512 1024 2048 4096 8192 16384 32768 65536 131072 262144 524288 1048576 2097152 4194304 8388608 16777216 33554432 67108864 134217728 268435456 536870912 1073741824 2147483648 4294967296 8589934592 17179869184 34359738368 68719476736 137438953472 274877906944 549755813888
 100
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 3 3 3 3 3 4 4 4 4 4 4 4 4 4 4 4 4 4 5 5 6 6 6 8 8 8 8 8 8 8 8 11 13 14
 41
1 1 2 4 8 16 32 64 128 256 512 1024 2048 4096 8192 16384 32768 65536 131072 262144 524288 1048576 2097152 4194304 8388608 16777216 33554432 67108864 134217728 268435456 536870912 1073741824 2147483648 4294967296 8589934592 17179869184 34359738368 68719476736 137438953472 274877906944 549755813888
 20
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 2 2
 1
1000000000000
 25
1 1 1 1 2 2 2 2 4 4 4 4 8 8 8 9 16 16 32 40 43 53 61 64 128
 41
1 2 4 8 16 32 64 128 256 512 1024 2048 4096 8192 16384 32768 65536 131072 262144 524288 1048576 2097152 4194304 8388608 16777216 33554432 67108864 134217728 268435456 536870912 1073741824 2147483648 4294967296 8589934592 17179869184 34359738368 68719476736 137438953472 274877906944 549755813888 1000000000000
 100
1 1 1 1 1 1 1 2 2 2 2 2 2 2 4 4 4 4 4 4 4 6 8 8 8 8 8 8 8 10 16 16 16 16 16 16 16 17 22 24 24 30 32 32 32 32 32 32 48 62 64 64 65 65 67 70 74 88 89 98 95 101 101 109 121 127 128 128 137 143 152 153 155 156 160 161 170 183 186 196 196 214 220 226 228 230 238 240 241 245 249 249 250 253 254 256 256 512 1024 1703
 8
1 1 2 2 4 4 5 8
 2
1 1001000000000
 25
1 1 1 1 2 2 2 2 4 4 4 4 8 8 8 8 13 15 16 11 31 32 36 41 55
 1
3
 101
1 1 1 1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 2 2 2 2 4 4 4 4 4 4 4 4 4 4 4 4 5 8 8 8 8 8 8 8 8 8 8 8 8 16 16 16 16 16 16 16 16 16 16 16 16 26 32 32 32 32 32 32 32 32 49 58 64 64 64 64 64 64 122 128 128 128 128 128 128 256 256 256 256 256 491 512 512 512 512 718 1024 2018 1024 2935 3123
 96
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 1 2 2 2 2 2 2 2 2 2 2 2 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 8 8 8 8 8 8 8 8 8 8 8 9 12 12 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 18 21
 40
1 2 4 8 16 32 64 128 256 512 1024 2048 4096 8192 16384 32768 65536 131072 262144 524288 1048576 750822 4194304 8388608 16777216 33554432 67108864 134217728 268435456 536870912 1073741824 2147483648 4294967296 8589934592 17179869184 34359738368 68719476736 137438953472 274877906944 549755813888
 41
1 1 4 4 8 16 32 64 128 256 512 1024 2048 4096 8192 16384 32768 65536 131072 262144 524288 1048576 2097152 4194304 8388608 16777216 33554432 67108864 134217728 268435456 536870912 1073741824 2147483648 4294967296 8589934592 17179869184 34359738368 68719476736 137438953472 274877906944 549755813888
 1
1001000000000
 25
1 1 1 1 2 3 2 2 4 4 4 4 8 8 8 9 16 16 32 40 43 53 61 64 128
 41
1 2 4 8 16 32 64 128 256 512 1024 2048 4096 8192 16384 32768 65536 131072 262144 524288 1048576 2097152 4194304 11747464 16777216 33554432 67108864 134217728 268435456 536870912 1073741824 2147483648 4294967296 8589934592 17179869184 34359738368 68719476736 137438953472 274877906944 549755813888 1000000000000
 5
1 2 4 3 4
 100
1 1 1 1 1 1 1 2 2 2 2 2 2 2 4 4 4 4 4 4 4 6 8 8 8 8 8 8 8 10 16 16 16 16 16 16 16 17 22 24 24 30 32 32 32 32 32 32 48 62 64 64 65 65 67 70 74 88 89 98 95 101 101 109 121 127 128 128 137 143 152 153 155 156 47 161 170 183 186 196 196 214 220 226 228 230 238 240 241 245 249 249 250 253 254 256 256 512 1024 1703
 2
1 1001000100000
 25
1 1 1 1 2 2 2 2 4 4 4 4 8 8 8 8 13 21 16 11 31 32 36 41 55
 1
6
 101
1 1 1 1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 2 2 2 2 4 4 7 4 4 4 4 4 4 4 4 4 5 8 8 8 8 8 8 8 8 8 8 8 8 16 16 16 16 16 16 16 16 16 16 16 16 26 32 32 32 32 32 32 32 32 49 58 64 64 64 64 64 64 122 128 128 128 128 128 128 256 256 256 256 256 491 512 512 512 512 718 1024 2018 1024 2935 3123
 96
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 1 2 2 2 2 2 2 2 2 2 2 2 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 8 8 8 8 8 8 8 8 8 8 8 9 12 12 16 16 16 16 16 16 16 13 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 18 21
 40
1 2 4 8 16 32 64 128 256 512 1024 2048 4096 8192 16384 32768 65536 131072 262144 524288 1048576 750822 4194304 8388608 16777216 33554432 67108864 134217728 268435456 536870912 1073741824 2147483648 849400235 8589934592 17179869184 34359738368 68719476736 137438953472 274877906944 549755813888
 41
1 1 4 4 8 16 32 64 128 256 11 1024 2048 4096 8192 16384 32768 65536 131072 262144 524288 1048576 2097152 4194304 8388608 16777216 33554432 67108864 134217728 268435456 536870912 1073741824 2147483648 4294967296 8589934592 17179869184 34359738368 68719476736 137438953472 274877906944 549755813888
 1
1001000010000
 25
1 1 1 1 2 3 2 2 4 4 4 4 8 8 8 9 16 16 32 54 43 53 61 64 128
 41
1 2 4 8 16 32 64 128 256 512 1024 2048 4096 8192 16384 32768 65536 131072 262144 524288 1048576 3172411 4194304 11747464 16777216 33554432 67108864 134217728 268435456 536870912 1073741824 2147483648 4294967296 8589934592 17179869184 34359738368 68719476736 137438953472 274877906944 549755813888 1000000000000
 8
1 1 2 4 3 4 5 8
 100
1 1 1 1 1 1 1 2 2 2 2 2 2 2 4 4 4 4 4 4 4 6 8 8 8 8 8 8 8 10 16 16 16 16 16 16 16 17 22 24 24 30 32 32 32 32 32 32 48 62 64 64 65 65 67 103 74 88 89 98 95 101 101 109 121 127 128 128 137 143 152 153 155 156 47 161 170 183 186 196 196 214 220 226 228 230 238 240 241 245 249 249 250 253 254 256 256 512 1024 1703
 2
1 0001000100000
 25
1 1 1 1 2 2 2 2 4 4 4 4 8 8 8 8 13 21 16 4 31 32 36 41 55
 1
4
 101
1 1 1 1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 2 2 2 2 4 4 7 4 4 4 4 4 4 4 4 4 5 8 8 8 8 8 8 8 8 8 8 8 8 16 16 16 16 16 16 16 16 16 16 16 16 26 32 32 32 32 32 32 32 32 49 58 64 64 64 64 64 64 122 128 128 128 128 128 128 256 256 256 256 256 491 512 512 512 512 718 66 2018 1024 2935 3123
 96
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 1 2 2 2 2 2 2 2 2 2 2 2 4 4 7 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 8 8 8 8 8 8 8 8 8 8 8 9 12 12 16 16 16 16 16 16 16 13 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 18 21
 40
1 2 4 8 16 32 64 128 256 512 1024 2048 4096 8192 16384 32768 56878 131072 262144 524288 1048576 750822 4194304 8388608 16777216 33554432 67108864 134217728 268435456 536870912 1073741824 2147483648 849400235 8589934592 17179869184 34359738368 68719476736 137438953472 274877906944 549755813888
 41
1 1 4 4 8 16 32 64 128 256 11 1024 2048 4096 8192 16384 32768 65536 131072 262144 524288 1048576 2097152 4194304 8388608 16777216 20091383 67108864 134217728 268435456 536870912 1073741824 2147483648 4294967296 8589934592 17179869184 34359738368 68719476736 137438953472 274877906944 549755813888
 1
1001000010100
 25
1 1 1 1 2 3 2 2 4 4 4 4 8 8 8 9 24 16 32 54 43 53 61 64 128
 41
1 2 4 8 16 32 64 128 256 512 1024 2048 4096 8192 16384 32768 65536 131072 180436 524288 1048576 3172411 4194304 11747464 16777216 33554432 67108864 134217728 268435456 536870912 1073741824 2147483648 4294967296 8589934592 17179869184 34359738368 68719476736 137438953472 274877906944 549755813888 1000000000000
 8
2 1 2 4 3 4 5 8
 100
1 1 1 1 1 1 1 2 2 2 2 2 2 2 4 4 4 4 4 4 4 6 8 3 8 8 8 8 8 10 16 16 16 16 16 16 16 17 22 24 24 30 32 32 32 32 32 32 48 62 64 64 65 65 67 103 74 88 89 98 95 101 101 109 121 127 128 128 137 143 152 153 155 156 47 161 170 183 186 196 196 214 220 226 228 230 238 240 241 245 249 249 250 253 254 256 256 512 1024 1703
 2
1 0001000000000
 25
1 1 1 1 2 2 2 2 4 4 4 4 8 8 8 3 13 21 16 4 31 32 36 41 55
 1
5
 101
1 1 1 1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 2 2 2 2 4 4 7 4 4 4 4 4 4 4 4 4 5 8 8 8 8 8 8 8 8 8 8 8 8 16 16 16 16 16 16 16 16 16 16 16 16 26 32 32 32 32 32 32 32 32 49 58 64 64 64 64 64 64 122 128 128 128 128 112 128 256 256 256 256 256 491 512 512 512 512 718 66 2018 1024 2935 3123
 96
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 1 2 2 2 2 2 2 2 2 2 2 2 4 4 7 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 8 8 8 8 8 8 8 8 8 8 8 11 12 12 16 16 16 16 16 16 16 13 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 18 21
 40
1 2 4 8 16 60 64 128 256 512 1024 2048 4096 8192 16384 32768 56878 131072 262144 524288 1048576 750822 4194304 8388608 16777216 33554432 67108864 134217728 268435456 536870912 1073741824 2147483648 849400235 8589934592 17179869184 34359738368 68719476736 137438953472 274877906944 549755813888
 41
1 1 4 4 8 16 32 64 128 256 11 1024 2048 4096 8192 16384 32768 65536 131072 262144 524288 365842 2097152 4194304 8388608 16777216 20091383 67108864 134217728 268435456 536870912 1073741824 2147483648 4294967296 8589934592 17179869184 34359738368 68719476736 137438953472 274877906944 549755813888
 1
1001001010100
 25
1 1 1 1 2 3 2 2 4 4 4 4 8 8 8 9 24 16 32 54 43 49 61 64 128
 41
1 2 4 8 16 32 54 128 256 512 1024 2048 4096 8192 16384 32768 65536 131072 180436 524288 1048576 3172411 4194304 11747464 16777216 33554432 67108864 134217728 268435456 536870912 1073741824 2147483648 4294967296 8589934592 17179869184 34359738368 68719476736 137438953472 274877906944 549755813888 1000000000000
 100
1 1 1 1 1 1 1 2 2 2 2 2 2 2 4 4 4 4 4 4 4 6 8 3 8 8 8 8 8 10 16 16 16 16 16 16 16 17 15 24 24 30 32 32 32 32 32 32 48 62 64 64 65 65 67 103 74 88 89 98 95 101 101 109 121 127 128 128 137 143 152 153 155 156 47 161 170 183 186 196 196 214 220 226 228 230 238 240 241 245 249 249 250 253 254 256 256 512 1024 1703
 2
1 1011000100000

2 3 
 2 
 -1
 1 
 -1
 1 2 
 -1
 -1
 -1
 1 
 -1
 5 
 4 
 11 12 
 -1
 1  27 28 29 30 31 32 33 34 35 36 37 38 
 1 2  9 10 11 12 13 14 15 16 17 
 -1
 -1
 1  -1
 2  -1
 -1
 -1
 -1
 -1
 -1
 -1
 -1
 -1
 -1
 -1
 -1
 -1
 -1
 -1
 -1
 -1
 -1
 -1
 -1
 -1
 -1
 -1
 -1
 -1
 -1
 -1
 -1
 -1
 -1
 -1
 -1
 -1
 -1
 -1
 -1
 -1
 -1
 -1
 -1
 -1
 -1
 -1
 -1
 -1
 -1
 -1
 -1
