跳到主要内容
图灵 OJTURING / ONLINE JUDGE

#F0891. Prairie Partition

  • ID: 897
  • 传统题
  • 2000ms
  • 256MiB
  • 尝试: 0
  • AC · 已通过: 0
  • 教学难度:提高
  • 上传者:
  • 二分
  • 构造
  • 贪心
  • 数学
  • 算法思想
  • 提高
  • 难度
  • 共享题库
  • Codeforces
  • 英文题面
  • 题目来源
  • 题面语言

Prairie Partition

题目描述

C. Prairie Partition
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

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].


题目来源:fps-www.educg.net-codeforce-1-2833.xml.zip;FPS 共享题包,题包内第 324 题。保留原作者与原赛事署名。