题目描述

给你 $n$ 个数，将它们分成任意组（可以不连续），将每个组内的数按位或，并将各组的结果累加，在保证其结果最小的情况下求最多分成的组数。

输入格式

第一行输入一个正整数 $n$。

第二行输入 $n$ 个非负整数 $a_i$。

输出格式

一个正整数，最优解中最多分成的组数。

6
1 1 4 5 1 4

1

7
1 9 1 9 8 1 0

2

8
1 9 2 6 0 8 1 7

2

9
3 1 4 1 5 9 2 6 5

1

9
9 9 8 2 4 4 3 5 3

1

6
1 2 3 4 8 12

2

提示

以下为各个样例的一种构造方案。

• $\{1,1,4,5,1,4\}$
• $\{1,9,1,9,8,1\},\{0\}$
• $\{1,9,2,6,8,1,7\},\{0\}$
• $\{3,1,4,1,5,9,2,6,5\}$
• $\{9,9,8,2,4,4,3,5,3\}$
• $\{1,2,3\},\{4,8,12\}$

对于样例 $6$ ，$\{1,2,3,4,8,12\}$ 也是一种最小化答案的方案，但是 $\{1,2,3\},\{4,8,12\}$ 分出的组数更多。

本题采用捆绑测试计分。

• Subtask $1$ ：$n\leq8$，$20$ 分。
• Subtask $2$ ：$n\leq10^3$，$20$ 分。
• Subtask $3$ ：$a_i\in\{0,1\}$，$5$ 分。
• Subtask $4$ ：$n=10^6$，且保证数据随机，$5$ 分。
• Subtask $5$ ：$n\leq10^6$，$30$ 分。
• Subtask $6$ ：$n\leq10^7$，$20$ 分。

对于所有数据，$0\leq a_i\leq10^{18}$，$1\leq n\leq10^7$。

如果你不知道什么是按位或，请点击这里。

本题自动开启O2优化。

本题提供读入优化方式。

使用 read(x); 读入一个任意的整型 x 等价于 scanf("%d", &x);其中可以将 %d 自动识别为对应类型。

#define getchar()(p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
char buf[1<<21],*p1=buf,*p2=buf;
template <typename T>
inline void read(T& r) {
	r=0;bool w=0; char ch=getchar();
	while(ch<'0'||ch>'9') w=ch=='-'?1:0,ch=getchar();
	while(ch>='0'&&ch<='9') r=r*10+(ch^48), ch=getchar();
	r=w?-r:r;
}