23630번 - 가장 긴 부분 수열 구하기 채점 준비 중

수 n 개로 이루어진 수열 A가 있다. 수열 A의 부분 수열 B는 어떤 조건을 갖는데, 조건은 다음과 같다. "수열 B의 길이는 1 이상이며, 수열 B에 속한 모든 수를 비트 and 연산을 한 결과값은 0이 아닌 수이다" 이때 나올 수 있는 수열 B 중, 길이가 가장 긴 수열을 수열 C라 하자. 수열 C의 길이를 출력하라.

예를 들어, 수열 A = {5, 6, 7, 11, 15}이라고 하고, A의 부분 수열 중 {5, 6, 11}을 볼 경우에는 5 & 6 & 11 = 0 이 되어 조건을 만족하지 않아 해당 부분 수열은 수열 B가 될 수 없다. (&는 비트 and 연산이다.) 하지만 A의 부분 수열 중 {5, 6, 7, 15}를 볼 경우에는 5 & 6 & 7 & 15 = 4 가 되어 조건을 만족하므로 해당 부분 수열은 수열 B가 될 수 있다. 또한, 해당 수열이 수열 B 중 가장 길이가 긴 수열이므로, 수열 C가 된다. 그러므로, 예제에 주어진 수열 A에 대한 출력값은 수열 C의 길이인 4가 된다.

첫 번째 줄에는 수열 A의 길이 n이 주어진다. (1 ≤ n ≤ 1,000,000) 두 번째 줄에는 수열 A의 각 원소 Ai가 공백으로 나뉘어서 주어진다. (1 ≤ i ≤ n, 1 ≤ A_i ≤ 1,000,000)

첫번째 줄에 수열 C의 길이를 출력한다.