시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 512 MB34117113458.772%

문제

$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$)

출력

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

예제 입력 1

5
5 6 7 11 15

예제 출력 1

4

출처

University > 경북대학교 > 2021 Goricon D번