다양한 부분 배열

Vanity의 선반에는 왼쪽부터 오른쪽까지 1, 2, ..., N으로 번호가 매겨진 장신구 N개가 있다. 장신구에는 여러 종류가 있으며, 각 종류는 양의 정수로 표시된다. 선반에 있는 i번째 장신구의 종류는 $A_{i}$이다.

Vanity는 오늘 해외에 있는 가족을 만나러 가며, 가능한 한 많은 장신구를 가져가고 싶어 한다. 하지만 서두르고 있으므로 Vanity는 연속한 구간의 장신구를 가져가야 한다. 엄밀히 말해, Vanity는 두 인덱스 l과 r을 선택하고 번호가 l, l+1, ..., r-1, r인 장신구를 모두 가져간다. 또한 세금 규정으로 인해, 선택한 구간에 어떤 종류의 장신구가 S개보다 많이 있으면 공항 보안 요원이 그 종류의 장신구를 모두 버린다.

예를 들어 S = 2이고 Vanity가 장신구 여섯 개, 즉 0 종류 한 개, 1 종류 두 개, 2 종류 세 개를 가져간다고 하자. 0 종류 장신구와 1 종류 장신구 두 개는 가지고 있을 수 있지만, 2 종류 장신구는 모두 잃게 된다!

Vanity는 가족에게 가져갈 수 있는 장신구의 수가 최대가 되도록 l과 r을 선택해야 한다. 가져갈 수 있는 장신구의 최대 개수는 얼마인가?

제한

시간 제한: 테스트 세트당 30초. 메모리 제한: 1GB. 1 ≤ T ≤ 100. 1 ≤ $A_{i}$ ≤ $10^{5}$. 1 ≤ S ≤ N.

테스트 세트 1 (공개)

1 ≤ N ≤ 1000.

테스트 세트 2 (비공개)

1 ≤ N ≤ $10^{5}$.

입력의 첫 줄에는 테스트 케이스의 수 T가 주어진다. 이어서 T개의 테스트 케이스가 주어진다. 각 테스트 케이스의 첫 줄에는 두 정수 N과 S가 주어지며, 각각 장신구의 개수와 허용되는 한 종류의 장신구 최대 개수를 나타낸다. 둘째 줄에는 N개의 정수가 주어진다. i번째 정수 $A_{i}$는 i번째 장신구의 종류를 나타낸다.

각 테스트 케이스마다 Case #x: y을 포함하는 한 줄을 출력한다. 여기서 x은 1부터 시작하는 테스트 케이스 번호이고, y는 Vanity가 가족에게 가져갈 수 있는 장신구의 최대 개수이다.

예제 케이스 #1에서 Vanity는 l = 2, r = 5를 선택해야 한다. 그러면 1, 4, 1, 4 종류의 장신구 4개를 공항으로 가져갈 수 있다. 공항 보안 요원이 버리는 장신구가 없으므로, 가족에게 장신구 4개를 가져갈 수 있다.

예제 케이스 #2에서 Vanity는 l = 1, r = 8를 선택해야 한다. 그러면 장신구 8개를 모두 공항으로 가져갈 수 있다. 500 종류 장신구는 S = 1개보다 많이 있으므로 버려지며, 따라서 가족에게 총 6개의 장신구를 가져갈 수 있다.

예제 케이스 #3에서 Vanity는 l = 1, r = 9를 선택해야 한다. 그러면 100, 200, 8, 8, 8, 8, 8, 300, 400 종류의 장신구 9개를 공항으로 가져갈 수 있다. 8 종류 장신구는 S = 1개보다 많이 있으므로 버려지며, 따라서 가족에게 총 4개의 장신구를 가져갈 수 있다.

예제 케이스 #4에서 Vanity는 l = 1, r = 12를 선택해야 한다. 그러면 장신구 12개를 모두 공항으로 가져갈 수 있다. 1 종류와 2 종류의 장신구는 각각 S = 2개보다 많이 있으므로 버려지며, 따라서 가족에게 총 6개의 장신구를 가져갈 수 있다.

참고: 이 문제에는 인터프리터 방식의 느린 언어를 사용하지 않는 것을 권장한다.