Problem Description

You are given $n$ numbers and need to divide them into any number of groups (which can be non-contiguous). For each group, perform a bitwise OR operation on the numbers within the group, and then sum the results of all groups. Your task is to find the maximum number of groups that can be formed while ensuring the sum is minimized.

Input Format

The first line contains a positive integer $n$.

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

Output Format

Output a single positive integer, which is the maximum number of groups in the optimal solution.

Sample Input and Output

Sample Input #1

6
1 1 4 5 1 4

Sample Output #1

1

Sample Input #2

7
1 9 1 9 8 1 0

Sample Output #2

2

Sample Input #3

8
1 9 2 6 0 8 1 7

Sample Output #3

2

Sample Input #4

9
3 1 4 1 5 9 2 6 5

Sample Output #4

1

Sample Input #5

9
9 9 8 2 4 4 3 5 3

Sample Output #5

1

Sample Input #6

6
1 2 3 4 8 12

Sample Output #6

2

Notes

Below are constructions 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\}$ results in more groups.

This problem uses bundled scoring.

• Subtask $1$: $n \leq 8$, $20$ points.
• Subtask $2$: $n \leq 10^3$, $20$ points.
• Subtask $3$: $a_i \in \{0,1\}$, $5$ points.
• Subtask $4$: $n = 10^6$, with guaranteed random data, $5$ points.
• Subtask $5$: $n \leq 10^6$, $30$ points.
• Subtask $6$: $n \leq 10^7$, $20$ points.

For all data, $0 \leq a_i \leq 10^{18}$, $1 \leq n \leq 10^7$.

If you are unfamiliar with the bitwise OR operation, please refer here.

O2 optimization is automatically enabled for this problem.

An input optimization method is provided.

Using read(x); to read any integer x is equivalent to scanf("%d", &x); where %d is 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;
}

见题面 Input 部分

见题面 Output 部分