Phoebe enjoys playing music. She especially enjoys playing it for her friends.
Phoebe has made a new musical instrument. The instrument is very much like a piano. It has N keys arranged in a straight line, numbered from 1 to N. The ith key has volume Vi. No two keys have the same volume and 1 ≤ Vi ≤ N. It takes |i-j| time to move from the ith key to the jth key on the instrument. Phoebe has a unique way of playing music. Immediately after playing key i, she can play only a key j such that:
-
j is not closer than K positions from key i (i.e. j should not be in the range [ i-K+1, i+K-1 ]).
-
Vj < Vi.
Each key may have 0 or more keys that can be played immediately after it.
Phoebe wants to find the summation of time required to go from each key i to the closest key that can be played after it. If there is no next playable key for a key i, then consider its time taken as 0.
Input:
The first line of the input contains T, the number of test cases.
The first line of each test case contains N and K.
The second line of each test case contains N integers of the array V.
Output:
For each test case, output a single number denoting the summation of time taken to move from each key i to the closest next playable key after i.
Constraints:
- 1 <= T <= 10
- 1 <= N <= 2 * 105
- 1 <= K,V[i] <= N
Second test case: The next playable keys for: 1 is { }. Closest=none, so time taken = 0 2 is { 1 }. Closest=1, so time taken = 1 3 is { 1 , 2 }. Closest=2, so time taken = 3 4 is { 1 , 2 , 3 }. Closest=2, so time taken = 1 5 is { 1 , 2 , 3 , 4 }. Closest=3 or 4, so time taken = 1 Total time taken is 6
Third test case: There is no key in range for keys 1-4. The next playable keys for: 1 is { } 2 is { } 3 is { } 4 is { } 5 is { 1 }. Closest = 1, So time taken = 4 Total time taken is 0+0+0+0+4=4
