가장 긴 부분 수열 구하기

시간 제한1초메모리 제한512 MB

요약

선택한 원소 전체의 비트 AND가 0이 아니게 되는 가장 긴 부분 수열의 길이를 구한다.

문제

$N$ 개의 자연수로 이루어진 수열 $A = \\{A\_1, A\_2, …, A\_N\\}$ 가 주어진다.

다음의 조건을 모두 만족하는 $A$ 의 부분 수열 $\\{A\_{i\_1}, A\_{i\_2}, ..., A\_{i\_m}\\}$ 중 가장 긴 수열의 길이를 출력하라.

$A\_{i\_1} \~\\&\~ A\_{i\_2} \~\\&\~ … \~\\&\~ A\_{i\_m} \neq 0$ ( $\\&$ : Bitwise AND)
$1 \leq i\_1 < i\_2 < … < i\_m \leq N$

예를 들어 $A = \\{5, 6, 7, 11, 15\\}$ 인 경우,

$\\{5, 6, 11\\}$ 은 조건 1을 만족하지 않는다. ( $0101\_{2} \~\\&\~ 0110\_{2} \~\\&\~ 1011\_{2} = 0000\_{2}$ )
$\\{5, 5\\}$ 는 조건 2를 만족하지 않는다. ( $i\_1 \nless i\_2$ )
$\\{5, 6, 7, 15\\}$ 는 조건을 모두 만족하는 가장 긴 부분 수열이다.

첫 번째 줄에는 수열 $A$ 의 길이를 나타내는 정수 $N$ 이 주어진다. 두 번째 줄에는 수열 $A$ 의 각 원소 $A\_i$ 가 공백으로 구분되어 주어진다.

첫 번째 줄에 조건을 모두 만족하는 가장 긴 부분 수열의 길이를 출력한다.