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⁵
1 ≤ K ≤ N × (N - 1) / 2
1 ≤ A[i] ≤ 10⁹

Example

Input:
5 3
5 4 3 2 1

Output:
6