AT_abc019_3.[ABC019C] 高橋くんと魔法の箱

高桥君有一个魔法箱。

如果将一个整数放入这个箱子，就会输出与之对应的另一个整数。

输出的整数只由放入的整数决定，每次放入相同的整数都会得到相同的结果。

高桥君发现，对于任意整数 $x$，将 $x$ 放入箱子和将 $2x$ 放入箱子时，输出的整数是相同的。

现在给定高桥君放入箱子的 $N$ 个整数，请你求出最多能得到多少种不同的输出整数。

输入通过标准输入按以下格式给出。

$N$ $a_1$ $a_2$ ... $a_N$

• 第 $1$ 行输入一个整数 $N\ (1 \leq N \leq 10^5)$，表示高桥君放入箱子的整数个数。
• 第 $2$ 行输入 $N$ 个用空格分隔的整数，表示高桥君放入箱子的整数 $a_1, a_2, ..., a_N$。
• 保证 $1 \leq a_i \leq 10^9\ (1 \leq i \leq N)$。
• 保证对于 $i \neq j$，有 $a_i \neq a_j$。

请输出最多能得到多少种不同的输出整数。

注意输出末尾需要换行。

部分分

本题设有部分分。

• 有 $20$ 分的测试点满足 $1 \leq N \leq 3,000$。
• 另有 $30$ 分的测试点满足 $1 \leq a_i \leq 5 \times 10^5\ (1 \leq i \leq N)$。

样例解释 1

将 $2$ 放入箱子时输出的整数与将 $1$ 放入箱子时相同，所以最多能得到 $2$ 种不同的输出整数。

样例解释 2

所有输入的整数最终输出的整数都相同。

样例解释 3

所有输出的整数都可能不同。

由 ChatGPT 4.1 翻译