Description

Given a sequence $a_i$ of length $n$, find the maximum length $k$ of a subsequence $b_i$ of $a_i$ such that $b_i \& b_{i-1} \ne 0$, where $2 \le i \le k$, and $\&$ denotes the bitwise AND operation.

Input Format

The input contains 2 lines. The first line contains an integer $n$. The second line contains $n$ integers, where the $i$-th integer is $a_i$.

Output Format

Output one line containing a single integer, the maximum length of the subsequence $b_i$.

3
1 2 3

2

Hint

For $100\%$ of the testdata, $1 \le n \le 100000$, $a_i \le 10^9$.

Translated by ChatGPT 5