2015 CodeCraft IIIT Hyderabad Replay |
---|
Finished |
Given an array of N integers A1, A2 ... AN 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 Ai, Ai + 1,..., Aj is defined as number of pairs (a, b) such that i ≤ a < b ≤ j and Aa > Ab.
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
4 1
1 2 4 0
3
2 0
1 2
3
Let’s denote by A[i, j] the subarray Ai, Ai + 1 ... Aj.
Example 1. A[1, 4], A[2, 4], A[3, 4] have at least 1 inversion.
Example 2. All subarrays are valid.
Name |
---|