401940: GYM100589 H Count Subarrays

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 < b ≤ j and A_a > A_b.

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

Print the required answer in one line.

Constraints

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

4 1
1 2 4 0

3

2 0
1 2

3

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.