题目描述

强哥在参加一场编程竞赛的培训，教练给他们讲解了一个关于二进制位运算的进阶问题。这个问题可以帮助他更好地理解计算机底层的数据处理方式。

现在有 $n$ 个正整数，每个数都可以看作是一个二进制串。强哥需要从这些数中选出一个子序列（不一定连续），要求在这个子序列中，相邻的两个数的二进制按位与（&）的结果不为0。换句话说，相邻两个数至少有一个二进制位都是 $1$。

这个问题的目标是找出满足条件的最长子序列的长度。

输入格式

输入文件共 $2$ 行。

第一行包括一个整数 $n$，表示正整数的个数。

第二行包括 $n$ 个整数，第 $i$ 个整数表示 $a_i$。

输出格式

输出文件共一行。

包括一个整数，表示满足条件的最长子序列的长度。

3
1 2 3

2

提示

对于 $100\%$ 的数据，$1\leq n\leq 100000$，$a_i\leq 10^9$。

样例解释： 对于序列 $[1, 2, 3]$，可以选择子序列 $[1, 3]$：

• $1$ 的二进制：$001$
• $3$ 的二进制：$011$
• $1 \& 3 = 001$（不为0） 所以最长长度为 $2$。