DCEPC14E - Inversion Play

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

Added by:dce coders
Date:2015-04-26
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:C CSHARP C++ 4.3.2 CPP CPP14 C99 GOSU JAVA PAS-GPC PAS-FPC PYTHON PYPY PYTHON3 PY_NBC

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.