Longest Subsequence with Nonzero Bitwise AND Adjacent Pairs

Given a sequence of n integers \(a_i\), find the maximum length \(k\) of a subsequence \(b_i\) (with \(1 \le i \le k\)) such that for every index \(i\) (where \(2 \le i \le k\)), the following condition holds:

\[ b_i \& b_{i-1} \ne 0 \]

Here, \(\&\) denotes the bitwise AND operation. A subsequence is derived from the original sequence by deleting some (or no) elements without changing the order of the remaining elements.

Your task is to compute and output the maximum possible value of \(k\).

inputFormat

The first line of input contains a single integer \(n\) (the length of the sequence). The second line contains \(n\) space-separated integers \(a_1, a_2, \dots, a_n\).

outputFormat

Output a single integer representing the maximum length \(k\) of a valid subsequence.

sample

5
1 2 3 4 5

3