可以证明,任何正整数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]。