#MX180. 集合操作

集合操作

时间限制:1000ms

空间限制:512MB

题目描述

给定非负整数可重集合 SS,你可以执行以下两种操作若干次:

  1. 选择两个非负整数 x,y∈Sx,y \in S,将 x∣yx|y 加入集合 SS,其中 ∣| 表示或运算。
  2. 选择两个非负整数 x,y∈Sx,y \in S,将 x&yx \& y 加入集合 SS,其中 &\& 表示与运算。

请最大化 SS 中不同数的个数,试输出 SS 中不同数最多可以有多少个。

输入格式

第一行一个正整数 nn,表示初始时 SS 中的个数。

之后 nn 个非负整数,依次表示 SS 集合中的元素 sis_i,元素可能有重复。

输出格式

输出一个非负整数,表示答案。

样例 1 输入

4
0 1 3 5

样例 1 输出

5

样例解释 1

最终集合 SS 中不同的数有 0,1,3,5,70,1,3,5,7。

样例 2 输入

3
1 3 5

样例 2 输出

4

样例 3~5

见下发文件。

数据规模与约定

对于 30%30\% 的数据,1≤n≤201 \leq n \leq 20。

对于另外 30%30\% 的数据,0≤si<2300 \leq s_i <2^{30}。

对于 100%100\% 的数据,1≤n≤105,0≤si<2401 \leq n \leq 10^5,0 \leq s_i <2^{40}。