You are given a sequence A (A[1],A[2],...A[n]) of size N. You have to create a new sequence B (B[1],B[2],...B[n]) of the same size N from the numbers given in sequence A. You are also given another number k (k>=0). The sequence B should be created in a way such that in sequence B, the number of pairs ( i , j ) , such that i < j and B[i] - B[j] > k is minimized. This minimum number for sequence B is called alpha number.

Now to form the sequence B , there are some rules. At any time we can pick an element either from the starting of sequence A or from the end of sequence A and remove that element. Now the element chosen from sequence A can be placed either at the starting or at the ending of sequence B formed till then. This operation is done N times to form the new sequence B.

For example, let's say given sequence A is {1,2,3,4} in beginning. Sequence B is empty{}.
A valid way of forming the sequence B:

Step 1 ------ A- {1,2,3} , B- {4}
Step 2 ------ A- {1,2} , B- {4,3}
Step 3 ------ A- {2} , B- {1,4,3}
Step 4 ------ A-{} , B- {1,4,3,2}

You have to print the alpha number in a new line.

Input Format

First line contains two integers N and k as described above. Next N lines contains an integer each - the elements of sequence A.

Output Format

Print the alpha number in a new line.

Constraints

1<= N<= 10^3
0<= A[i],k<= 10^5