카운트다운
면접 대비시간 제한20초메모리 제한1024 MB
길이가 K이면서 K, K-1, ..., 2, 1 순서로 감소하는 연속 부분 배열의 개수를 센다.
문제
Avery는 N개의 양의 정수로 이루어진 배열을 가지고 있다. 배열의 i번째 정수는 Ai이다.
어떤 연속 부분 배열이 길이 m이고 m, m-1, m-2, ..., 2, 1을 그 순서대로 포함하면 그 부분 배열을 m-카운트다운이라고 한다. 예를 들어 [3, 2, 1]은 3-카운트다운이다.
Avery의 배열에 있는 K-카운트다운의 개수를 셀 수 있는가?
입력
입력의 첫 줄에는 테스트 케이스의 수 T가 주어진다. T개의 테스트 케이스가 이어진다. 각 테스트 케이스의 첫 줄에는 정수 N과 K가 주어진다. 둘째 줄에는 N개의 정수가 주어진다. i번째 정수는 Ai이다.
출력
각 테스트 케이스마다 Case #x: y 형식의 한 줄을 출력한다. 여기서 x는 테스트 케이스 번호(1부터 시작)이고 y는 배열에 있는 K-카운트다운의 개수이다.
제한
- 1 ≤ T ≤ 100.
- 2 ≤ K ≤ N.
- 모든 i에 대해 1 ≤ Ai ≤ 2 × 105.
힌트
예제 1에는 아래에 표시된 것처럼 두 개의 3-카운트다운이 있다.
- 1 2 3 7 9 3 2 1 8 3 2 1
- 1 2 3 7 9 3 2 1 8 3 2 1
예제 2에는 2-카운트다운이 없다.
예제 3에는 아래에 표시된 것처럼 하나의 6-카운트다운이 있다.
- 100 7 6 5 4 3 2 1 100