Given an array of N integers A₁, A₂ ... A_N and an integer K, count number of subarrays of A such that number of inversions in those subarrays is at least K.
Inversions in a subarray A_i, A_i+1 ... A_j is defined as number of pairs (a,b) such that i = a and A_a > A_b.

Input

First line consists of N and K in single line. Next line contains N space separated integers denoting array A.

 

Output

Print the required answer in one line.

Constraints

Should contain all the constraints on the input data that you may have. Format it like:

• 1 = N = 10⁵
• 0 = A_i = 10⁹
• 0 = K = N*(N-1)/2

 

Example

Input 1: 4 1 1 2 4 0 Input 2: 2 0 1 2 Output 1: 3 Output 2: 3

 

Explanation

Let’s denote by A[i,j] the subarray A_i, A_i+1 ... A_j.

Example 1.
A[1,4], A[2,4], A[3,4] have at least 1 inversion.

Example 2.
All subarrays are valid.

Note: Large input files. Use scanf/printf instead of cin/coun