CF949E Binary Cards

玩“二进制卡牌”游戏永远都不嫌晚！ 在这个游戏中，有无限数量的正负等级卡牌。任何卡牌的等级的绝对值都是 $2^{k}$ 的形式，也就是说，每张卡牌的等级都是 $2^{k}$ 或 $-2^{k}$，其中 $k \geq 0$ 且为整数。每种合法等级的卡牌数量都是无限的。 游戏开始时，玩家需要组建自己的卡组，这个卡组是一些卡牌组成的多重集（可以为空）。你可以选择任意数量、任意等级的卡牌，但卡组越小越能体现你的技巧。游戏共进行 $n$ 轮。在第 $i$ 轮，裁判会告诉玩家一个整数 $a_{i}$。此后，玩家必须从自己的卡组中抽取一个子集，使得所选卡牌的等级和恰好等于 $a_{i}$（也可以一张卡都不抽，此时和视为 $0$）。如果玩家无法做到这一点，则游戏失败，立即结束。否则，玩家将所有卡牌收回卡组，游戏进入下一轮。如果每一轮都能成功抽出合适的卡牌集合，玩家即获胜。 现在你已经知道了每一轮裁判会告诉你的数字 $a_{i}$。你希望选择一个包含最少卡牌数量的卡组，使你能够赢得“二进制卡牌”游戏。

输入的第一行包含一个整数 $n$（$1 \leq n \leq 100000$），表示游戏的轮数。 输入的第二行包含 $n$ 个整数 $a_{1}, a_{2}, \ldots, a_{n}$（$-100000 \leq a_{i} \leq 100000$），表示每一轮裁判会告诉你的数字。

输出第一行包含一个整数 $k$（$0 \leq k \leq 100000$），表示你需要选择的最小卡牌数量。 输出第二行包含 $k$ 个整数 $b_{1}, b_{2}, \ldots, b_{k}$（$-2^{20} \leq b_{i} \leq 2^{20}$，$|b_{i}|$ 是 $2$ 的幂），表示你卡组中每张卡牌的等级。你可以按任意顺序输出这些等级。如果存在多个最优解，你可以输出其中任意一个。 保证一定存在满足所有要求的最小卡组。

在第一个样例中，游戏只有一轮，你可以直接抽出你的两张卡牌。注意，这个样例是唯一满足第一测试组约束的样例。 在第二个样例中，你可以在第一轮抽出唯一的一张 $-1$ 卡牌，在第二轮抽出 $4$ 和 $-1$ 卡牌，在第三轮不抽卡牌，在第四轮抽出唯一的 $4$ 卡牌，在第五轮抽出整个卡组。 由 ChatGPT 4.1 翻译