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 翻译