普及模拟赛 20 - E

题目描述

给定非负整数可重集合 $S$，你可以执行以下两种操作若干次：

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

请最大化 $S$ 中不同数的个数，试输出 $S$ 中不同数最多可以有多少个。

输入描述

第一行一个正整数 $n$，表示初始时 $S$ 中的个数。

之后 $n$ 个非负整数，依次表示 $S$ 集合中的元素 $s_i$，元素可能有重复。

输出格式

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

样例输入1

4
0 1 3 5

样例输出1

5

样例解释1

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

样例输入2

3
1 3 5

样例输出2

4

样例输入3,4,5

见下发文件。

样例输出3,4,5

见下发文件。

数据范围

对于 $30\%$ 的数据，$1 \leq n \leq 20$。

对于另外 $30\%$ 的数据，$0 \leq s_i <2^{30}$。

对于 $100\%$ 的数据，$1 \leq n \leq 10^5,0 \leq s_i <2^{40}$。