Rounddog를 행복하게 만들기

Rounddog는 오른쪽 주머니에 항상 배열 $a_1, a_2, \ldots, a_n$을 넣고 다니며, 이 배열은 $1 \le a_i \le n$을 만족한다.

부분 배열이란 원래 배열의 비어 있지 않은 연속한 구간이다. Rounddog는 구간 $a_l, a_{l+1}, \ldots, a_r$에 있는 모든 원소가 서로 다르고 $\max(a_l, a_{l+1}, \ldots, a_r) - (r - l + 1) \le k$를 만족할 때 이 구간을 좋은 부분 배열이라고 정의한다.

Rounddog는 오늘 행복하지 않다. 그의 가장 친한 친구인 당신은 그를 행복하게 만들기 위해 $a$의 모든 좋은 부분 배열을 찾으려 한다. $a$의 좋은 부분 배열의 개수를 구하시오.

입력은 여러 테스트 케이스로 이루어지며, 첫째 줄에 테스트 케이스의 수 $T$ ($1 \le T \le 20$)가 주어진다.

각 테스트 케이스의 첫째 줄에는 두 정수 $n$ ($1 \le n \le 300\,000$)과 $k$ ($1 \le k \le 300\,000$)가 주어진다.

둘째 줄에는 $n$개의 정수가 주어지며, $i$번째 정수는 $a_i$ ($1 \le a_i \le n$)이다.

모든 테스트 케이스에서 $n$의 합은 $1\,000\,000$을 넘지 않는다.

각 테스트 케이스마다 주어진 배열의 좋은 부분 배열 개수를 한 줄에 하나씩 출력한다.