23630번 - 가장 긴 부분 수열 구하기

문제

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

다음의 조건을 모두 만족하는 $A$의 부분 수열 $\{A_{i_1}, A_{i_2}, ..., A_{i_m}\}$ 중 가장 긴 수열의 길이를 출력하라.

1. $A_{i_1} ~\&~ A_{i_2} ~\&~ … ~\&~ A_{i_m} \neq 0$ ($\&$: Bitwise AND)
2. 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$가 공백으로 구분되어 주어진다.

• 1ドル \leq N \leq 1,000,000$
• 1ドル \leq A_i \leq 1,000,000$ (1ドル \leq i \leq N$)

출력

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

제한

힌트