問題文
高桥君有一个魔法盒。
如果您在此框中输入一个整数,则会出现相应的整数。
出来的整数仅由您输入的整数决定,如果您输入相同的整数,则每次都会得到相同的结果。
Takahashi-kun 可以是任何整数 关于 x , 当我输入x 我注意到当我输入 2x 时,出来的整数是相同的。
高桥君输入的整数是 给出了 N ,所以请回答可以出现的最大整数个数。
入力
输入是按以下格式从标准输入给出的。
N a_1 a_2 .. a_N
- 1 高桥放入框中的整数个数显示在第一行。 N ( 1 ≦ N ≦ 10^5) 。 表示
- 2 在这一排,高桥君把它放进了盒子里。 N 给出整数,用空格分隔。
- 1 ≦ a_i ≦ 10^9 ( 1 ≦ i ≦ N) 有保证。 当
- i ≠ j 时,a_i ≠ a_j 有保证。 当
出力
将可以出现的最大整数数输出到标准输出。
不要忘记最后的换行符。
部分点
针对此问题设置了部分分数。
- 20 在点的测试用例中,1 ≦ N ≦ 3,000 很满意。
- 另一个 输入 30 在点的测试用例中,1 ≦ a_i ≦ 5*10^5 ( 1 ≦ i ≦ N) 很满意。
入力例1
3 1 2 3
出力例1
2
2 时出现的整数是 它等于输入1 时得到的整数,所以最大值是 2 整数类型。
入力例2
4 2 4 8 16
出力例2
1
将出现所有相同的整数。
入力例3
4 2 3 5 7
出力例2
4
出现的整数可能都不同。