23905번 - Countdown 서브태스크다국어

문제

Avery has an array of N positive integers. The i-th integer of the array is A_i.

A contiguous subarray is an m-countdown if it is of length m and contains the integers m, m-1, m-2, ..., 2, 1 in that order. For example, [3, 2, 1] is a 3-countdown.

Can you help Avery count the number of K-countdowns in her array?

입력

The first line of the input gives the number of test cases, T. T test cases follow. Each test case begins with a line containing the integers N and K. The second line contains N integers. The i-th integer is A_i.

출력

For each test case, output one line containing Case #x: y, where x is the test case number (starting from 1) and y is the number of K-countdowns in her array.

제한

• 1 ≤ T ≤ 100.
• 2 ≤ K ≤ N.
• 1 ≤ A_i ≤ 2 × 10⁵, for all i.

Test Set 1 (5점)

• 2 ≤ N ≤ 1000.

Test Set 2 (7점)

• 2 ≤ N ≤ 2 × 10⁵ for at most 10 test cases.
• For the remaining cases, 2 ≤ N ≤ 1000.

힌트

In sample case #1, there are two 3-countdowns as highlighted below.

• 1 2 3 7 9 3 2 1 8 3 2 1
• 1 2 3 7 9 3 2 1 8 3 2 1

In sample case #2, there are no 2-countdowns.

In sample case #3, there is one 6-countdown as highlighted below.

• 100 7 6 5 4 3 2 1 100