← 返回题目列表

Codeforces · 773/C

C. 草原分区

中文机器翻译题面 查看原题

可以证明,任何正整数x都可以唯一表示为x = 1 + 2 + 4 + ... + 2k - 1 + r,其中k和r是整数,k ≥ 0,0 < r ≤ 2k。我们将该表示称为 x 的草原分区。

例如12、17、7、1的草原分区为:

12 = 1 + 2 + 4 + 5,17 = 1 + 2 + 4 + 8 + 2,7 = 1 + 2 + 4,1 = 1.

Alice 取一个正整数序列(可能带有重复元素),用其草原分区中的被加数序列替换每个元素,以非递减顺序排列结果数字并将它们交给 Borys。现在鲍里斯想知道爱丽丝的原始序列可以包含多少元素。找出所有可能的选项!

输入

第一行包含一个整数 n (1 ≤ n ≤ 105) — Alice 给 Borys 的数字数量。

第二行包含 n 个整数 a1, a2, ..., an (1 ≤ ai ≤ 1012; a1 ≤ a2 ≤ ... ≤ an) — Alice 给 Borys 的数字。

输出

按升序输出 m 的所有可能值,使得存在长度为 m 的正整数序列,如果将每个元素替换为其草原分区中的被加数,并按非降序排列结果数字,您将得到输入中给出的序列。

如果不存在这样的 m 值,则输出单个整数 -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

注意

在第一个示例中,Alice 可以从 [6, 20] 中获取输入序列作为原始序列。

在第二个示例中,Alice 的原始序列可以是 [4, 5] 或 [3, 3, 3]。