Prairie Partition

题意翻译

对于每个正整数 $n$，可以将其分为 $1+2+4+8+16+\cdots+2^k+r$。 如 $17=1+2+4+8+2,7=1+2+4$。 给你 $n$ 个递增的数构成的串 $a$，这串数是由几个数的拆分放在一起构成的。 如 $6,20$ 的串为 $1,1,2,2,3,4,5,8 $。 问这个串是由几个数构成的。输出所有方案，无解输出 $-1$。 $1\le n\le 10^5,1\le a_i\le 10^{12}$

题目描述

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&lt;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!

输入输出格式

输入格式

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

输入输出样例

输入样例 #1

8
1 1 2 2 3 4 5 8

输出样例 #1

2 

输入样例 #2

6
1 1 1 2 2 2

输出样例 #2

2 3 

输入样例 #3

5
1 2 4 4 4

输出样例 #3

-1

说明

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

题意翻译

对于每个正整数 $n$，可以将其分为 $1+2+4+8+16+\cdots+2^k+r$。 如 $17=1+2+4+8+2,7=1+2+4$。 给你 $n$ 个递增的数构成的串 $a$，这串数是由几个数的拆分放在一起构成的。 如 $6,20$ 的串为 $1,1,2,2,3,4,5,8 $。 问这个串是由几个数构成的。输出所有方案，无解输出 $-1$。 $1\le n\le 10^5,1\le a_i\le 10^{12}$