18608번 - Make Rounddog Happy 다국어

문제

Rounddog always has an array a₁, a₂, . . . , a_n in his right pocket, satisfying 1 ≤ a_i ≤ n.

A subarray is a non-empty subsegment of the original array. Rounddog defines a good subarray as a subsegment a_l, a_l+1, . . . , a_r such that all elements in it are different and max(a_l, a_l+1, . . . , a_r) − (r − l + 1) ≤ k.

Rounddog is not happy today. As his best friend, you want to find all good subarrays of a to make him happy. For this problem, please calculate the total number of good subarrays of a.

입력

The input contains several test cases, and the first line contains a single integer T (1 ≤ T ≤ 20), the number of test cases.

The first line of each test case contains two integers n (1 ≤ n ≤ 300 000) and k (1 ≤ k ≤ 300 000).

The second line contains n integers, the i-th of which is a_i (1 ≤ a_i ≤ n).

It is guaranteed that the sum of n over all test cases never exceeds 1 000 000.

출력

For each test case, print a single line with a single integer: the number of good subarrays in the given array.

제한

힌트