P7384 "EZEC-6" Grouping

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.

The first line contains a positive integer $n$. The second line contains $n$ non-negative integers $a_i$.

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

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](https://baike.baidu.com/item/%E6%8C%89%E4%BD%8D%E6%88%96). 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. ```cpp #define getchar()(p1==p2&&(p2=(p1=buf)+fread(buf,1,1