There is an array A of n elements. You need to tell the number of subarrays having inversion count greater than equal to a particular value K.

Input

The first line will contain two space separated integers N and K.

The next line will contain N space separated integers representing the elements of the array.

Output

Print the answer to the given problem in one line.

Constraints

1 <= N <= 10^5
1 <= K <= N * (N - 1) / 2
1 <= A[i] <= 10^9

Example

Input:
5 3
5 4 3 2 1

Output:
6