*Phoebe's Melody

Phoebe's Melody

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 V_i. No two keys have the same volume and 1 ≤ V_i ≤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 ]).
• V_j < V_i.

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⁵
• 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

----------------------------------------------------------------------------EDITORIAL--------------------------------------------------

THIS IS A simple lower bound concept , but we need to do it ins a good way, a number can only pair with a number which is at a  distance k from the numbers and must be less than the number soo lets process number in the sorted order , and after processing ans  of a number , insert index of this number , so that when a new number comes that number  must be > than this number , and it can use this number,s index to pair with this number , we insert it in a set so that it  indexes will be in a sorted order so that we can easily find  first index near to index i ie(<=i-k  and >i+k)

------------------------------------------------------------------code----------------------------------------------------------------------

#include<bits/stdc++.h>
using namespace std;

int main()
 {
  int t;
   cin>>t;
   while(t--)
   {
    vector<pair<int,int> > v;
        set<int> vs;
    int n,k;
    scanf("%d %d",&n,&k);
    for(int i=1;i<=n;i++)
     {
      int a;
      scanf("%d",&a);
      v.push_back(make_pair(a,i));
     
}
sort(v.begin(),v.end());
long long int ans=0;
vs.insert(v[0].second);
for(int i=1;i<n;i++)
 {
  int temp=100000000;
  int num=v[i].first;
  int pos=v[i].second;
  int bb=pos-k;
  int ff=pos+k;
  set<int>:: iterator back,front;
   
  back=vs.lower_bound(bb);
  int f=0;
  if((back==vs.end() || *back>bb))
  {
  if(back==vs.begin()) f=1;
  back--;
  }
 
  if(f==0 && bb>=1)
    {
    temp=abs(pos-*back);
}
  front=vs.lower_bound(ff);
  if(front!=vs.end()  && ff<=n)
   {
    temp=min(temp,abs(pos-*front));
}
if(temp!=100000000)
{
ans+=temp;
}
vs.insert(pos);
 }
  printf("%lld\n",ans);
 
  }
 }