다양한 부분배열
시간 제한30초메모리 제한1024 MB
구슬 종류 배열과 상한 S가 주어질 때, 각 종류가 구간 안에서 S번 이하로 등장하는 원소 수를 최대로 만드는 연속 구간을 고른다.
문제
Vanity는 선반에 N개의 장식품을 왼쪽에서 오른쪽으로 1, 2, ..., N번까지 번호를 붙여 놓았다. 장식품은 여러 종류이며, 종류는 양의 정수로 나타낸다. 선반의 i번째 장식품의 종류는 Ai이다.
그녀는 오늘 해외에 있는 가족을 만나러 가므로, 장식품을 최대한 많이 가져가려고 한다. 하지만 시간이 없어서 Vanity는 연속된 구간의 장식품만 가져갈 수 있다. 즉, Vanity는 두 인덱스 l과 r을 골라 l, l+1, ..., r-1, r번 장식품을 모두 가져간다. 또한 세금 규정 때문에, 고른 구간에서 어떤 종류의 장식품이 S개를 초과하면 공항 보안 검색에서 그 종류의 장식품을 모두 버린다.
예를 들어 S = 2이고 Vanity가 여섯 개의 장식품, 즉 종류 0이 하나, 종류 1이 둘, 종류 2가 셋을 가져간다고 하자. 그러면 종류 0 장식품 하나와 종류 1 장식품 둘은 가질 수 있지만, 종류 2 장식품은 모두 잃게 된다!
Vanity는 가족에게 가져갈 장식품 수가 최대가 되도록 l과 r을 골라야 한다. 가져갈 수 있는 장식품 수의 최댓값은 얼마인가?
입력
입력의 첫 줄에는 테스트 케이스의 수 T가 주어진다. T개의 테스트 케이스가 이어진다. 각 테스트 케이스의 첫 줄에는 장식품의 수 N과 한 종류에 허용되는 최대 장식품 수 S가 주어진다. 둘째 줄에는 N개의 정수가 주어진다. i번째 정수는 i번째 장식품의 종류 Ai이다.
출력
각 테스트 케이스마다 Case #x: y 형식의 한 줄을 출력한다. 여기서 x는 테스트 케이스 번호(1부터 시작)이고 y는 Vanity가 가족에게 가져갈 수 있는 장식품 수의 최댓값이다.
제한
- 1 ≤ T ≤ 100.
- 1 ≤ Ai ≤ 105.
- 1 ≤ S ≤ N.
힌트
Sample Case #1에서 Vanity는 l = 2, r = 5를 골라야 한다. 그러면 종류가 1, 4, 1, 4인 장식품 4개를 공항까지 가져갈 수 있다. 공항 보안 검색에서 버려지는 장식품이 없으므로 가족에게 장식품 4개를 가져갈 수 있다.
Sample Case #2에서 Vanity는 l = 1, r = 8를 골라야 한다. 그러면 장식품 8개를 모두 공항까지 가져갈 수 있다. 종류 500인 장식품은 S = 1보다 많으므로 버려지고, 따라서 모두 6개의 장식품을 가족에게 가져갈 수 있다.
Sample Case #3에서 Vanity는 l = 1, r = 9를 골라야 한다. 그러면 종류가 100, 200, 8, 8, 8, 8, 8, 300, 400인 장식품 9개를 공항까지 가져갈 수 있다. 종류 8인 장식품은 S = 1보다 많으므로 버려지고, 따라서 모두 4개의 장식품을 가족에게 가져갈 수 있다.
Sample Case #4에서 Vanity는 l = 1, r = 12를 골라야 한다. 그러면 장식품 12개를 모두 공항까지 가져갈 수 있다. 종류 1과 종류 2인 장식품은 각각 S = 2보다 많으므로 버려지고, 따라서 모두 6개의 장식품을 가족에게 가져갈 수 있다.
참고: 이 문제에는 인터프리터 언어나 느린 언어를 사용하지 않는 것을 권장한다.