Description

You are given $n$ numbers. Split them into any number of groups (they do not need to be contiguous). For each group, take the bitwise OR of the numbers in that group, and then sum the results of all groups. Under the condition that this total sum is minimized, find the maximum possible number of groups.

Input Format

The first line contains a positive integer $n$.

The second line contains $n$ non-negative integers $a_i$.

Output Format

Output one positive integer: the maximum number of groups in an optimal solution.

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

Hint

Below is one possible construction for each sample.

• $\{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\}$

For sample $6$, $\{1,2,3,4,8,12\}$ is also a solution that minimizes the answer, but $\{1,2,3\},\{4,8,12\}$ produces more groups.

This problem uses bundled test scoring.

• Subtask $1$: $n\leq8$, $20$ points.
• Subtask $2$: $n\leq10^3$, $20$ points.
• Subtask $3$: $a_i\in\{0,1\}$, $5$ points.
• Subtask $4$: $n=10^6$, and the testdata is guaranteed to be random, $5$ points.
• Subtask $5$: $n\leq10^6$, $30$ points.
• Subtask $6$: $n\leq10^7$, $20$ points.

Constraints: for all testdata, $0\leq a_i\leq10^{18}$, $1\leq n\leq10^7$.

If you do not know what bitwise OR is, please click here.

This problem enables O2 optimization by default.

This problem provides an input optimization method.

Using read(x); to read any integer x is equivalent to scanf("%d", &x);, where %d can be automatically recognized as the corresponding type.

#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;
}

Translated by ChatGPT 5