#P18462. AND-OR closure

AND-OR closure

AND-OR closure

给定一个包含 nn 个非负整数的集合 AA,定义它的 AND-OR 闭包为满足以下条件、元素个数最少的集合 BB:

  • A⊆BA\subseteq B。
  • 如果 x,y∈Bx,y\in B,则 xANDy∈Bx\mathbin{\mathrm{AND}}y\in B。
  • 如果 x,y∈Bx,y\in B,则 xORy∈Bx\mathbin{\mathrm{OR}}y\in B。

求 AA 的 AND-OR 闭包的元素个数。

这里 AND 表示按位与运算,OR 表示按位或运算。闭包中的元素可以继续参与运算;集合中相同的整数只计一次。

输入格式

第一行包含一个整数 nn(1≤n≤2×1051\le n\le2\times10^5),表示集合 AA 的元素个数。

第二行包含 nn 个两两不同的整数 a1,a2,…,ana_1,a_2,\ldots,a_n(0≤ai<2400\le a_i<2^{40}),表示集合 AA 的元素。

输入只有一个集合,没有多组数据或额外的跨用例总限制。

输出格式

输出一个整数,表示 AA 的 AND-OR 闭包的元素个数。答案不取模,可能超过 32 位整数范围。

原样例 1

4
0 1 3 5
5

原样例 2

5
0 1 2 3 4
8

原样例说明

第一个样例的 AND-OR 闭包是 {0,1,3,5,7}\{0,1,3,5,7\}。

第二个样例的 AND-OR 闭包是 {0,1,2,3,4,5,6,7}\{0,1,2,3,4,5,6,7\}。