phoebes-melody-1

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 i^th key has volume Vi. No two keys have the same volume and 1 ≤ Vi ≤ N. It takes |i-j| time to move from the i^th key to the j^th 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 * 10^5
1 ≤ K,V[i] ≤ N

SAMPLE INPUT
3
2 1
1 2 
5 1
3 5 4 2 1 
5 4
1 2 3 4 5

SAMPLE OUTPUT
1
6
4

Explanation

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

Source: hackerearth | Difficulty: MEDIUM
Tags: Dynamic programming

Data structures


Solutions: