给你一组 Y,其中包含 n 个不同的正整数 y1, y2, ..., yn。
如果可以通过将以下两个运算中的一些应用于 X 中的整数来将 X 转换为 Y,则 n 个不同正整数 x1, x2, ..., xn 的集合 X 被称为生成集合 Y:
1. 取任意整数 xi 并将其乘以 2,即将 xi 替换为 2·xi。
2. 取任意整数xi,将其乘以2并加1,即将xi替换为2·xi + 1。
请注意,X 中的整数不需要在每次操作后都不同。
如果两组不同的整数 X 和 Y 相等,则它们相等。换句话说,如果我们按升序将集合的元素写入数组,则这些数组将相等。
请注意,任何整数集(或其排列)都会自行生成。
给定一个集合 Y,并且必须找到一个生成 Y 的集合 X,并且 X 的最大元素是可能的最小值。
输入
输入的第一行包含一个整数 n (1 ≤ n ≤ 50 000) - Y 中的元素数量。
第二行包含 n 个整数 y1, ..., yn (1 ≤ yi ≤ 109),保证不同。
输出
打印 n 个整数 — 生成 Y 的不同整数集,且其中的最大元素是可能的最小值。如果有多个这样的集合,则打印其中任意一个。
示例
输入 #1
5 1 2 3 4 5
输出 #1
4 5 2 3 1
输入 #2
6 15 14 3 13 1 12
输出 #2
12 13 14 7 3 1
输入 #3
6 9 7 13 17 5 11
输出 #3
4 5 2 6 3 1