문제 설명
부분 수열(subsequence)은 주어진 수열에 있는 수로 구성되는 수열로 순서를 유지해야 하지만 순서에 있는 수 중 일부는 포함하지 않을 수 있다. 예를 들어, [1 5 2 4]가 주어지면 [1 2 4], [5 4], [2], [1 5 2 4] 등은 부분 수열에 해당한다.
주어진 수열에서 가장 긴 조화 부분 수열을 찾아주세요. 조화 부분 수열이란 부분 수열에 구성하는 요소에서 가장 작은 값과 큰 값의 차이가 정확하게 1인 경우를 말한다. 예를 들어, [1 5 2 1 2 4]이면 [1 2], [1 2 1 2], [5 4] 등은 조화 부분 수열이다. 하지만 [1 1] [5] [5 2] [2 2] 등은 조화 부분 수열이 아니다.
입력 설명
첫 줄에는 테스트케이스 T(1<=T<=100)가 주어지고, 각 테스트케이스는 두 줄로 주어집니다. 테스트케이스의 첫 줄에는 수열의 길이 N(1<=N<=20,000)이 주어지고, 둘째 줄에는 N개의 정수 X(-1,000,000<=X<=1,000,000)가 주어집니다.
출력 설명
각 테스트케이스마다 가장 긴 조화 순열의 길이를 출력하여 주세요.
3
8
1 3 2 2 5 2 3 7
6
-3 -1 -1 -1 -3 -2
4
2 2 2 2