손에 든 카드를 연속된 숫자 묶음으로 나누어 가장 짧은 묶음을 최대한 길게 만듭니다.
보통5백트래킹정렬면접 대비아직 제출이 없습니다시간 제한5초메모리 제한512 MB카드마다 정수 하나가 적혀 있는 카드 게임을 한다.
게임을 시작하면 카드 몇 장을 손에 받는다. 손에 든 카드는 한 장도 남기지 않고 여러 개의 스트레이트로 나눈다. 스트레이트는 값이 연속하는 카드의 집합이다. 예를 들어 카드 세 장으로 이루어진 {3, 4, 5}도 스트레이트고, 카드 한 장뿐인 {7}도 스트레이트다. 카드를 다 나누면 가장 짧은 스트레이트의 길이와 같은 금액을 달러로 받는다. 손에 카드가 없으면 스트레이트를 하나도 만들 수 없으므로 0달러를 받는다.
테스트 케이스마다 손에 든 카드가 주어진다. 각 테스트 케이스에서 받을 수 있는 최대 금액을 구한다.
첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어진다. 각 줄에는 손에 든 카드의 개수 N과 그 카드에 적힌 정수 N개가 공백으로 구분되어 주어진다.
각 테스트 케이스마다 Case #x: y 형식으로 한 줄씩 출력한다. x는 1부터 시작하는 테스트 케이스 번호이고, y는 그 테스트 케이스에서 받을 수 있는 최대 금액이다.
예제 입력의 첫 번째 케이스에는 1부터 10까지 적힌 카드 열 장이 있다. 길이가 10인 스트레이트 하나를 만들어 10달러를 받는다.
두 번째 케이스를 {101, 102, 103, 104, 105, 106}과 {103, 104}로 나누면 2달러를 받는다. 하지만 {101, 102, 103, 104}와 {103, 104, 105, 106}으로 나누면 4달러를 받는다.
세 번째 케이스는 카드가 없으므로 0달러다.
네 번째 케이스에서 9가 적힌 카드는 자기 혼자 있는 스트레이트에 들어가야 한다. 그래서 1달러를 받는다.