SOLVE
LATER
Let's define 2 functions a function \(F(i)\) and \(Val(i,j)\) for an Array A of size N as follows:
\(F(i) =\) \( \sum_{j=i+1}^{N} Val(i,j) \)
\( Val(i,j) =\) 1 ,if \(A[i] < A[j]\), else, \(Val(i,j) =\) 0.
Now, Vanya has been given one such array A of size N and an integer K. She needs to find the number of Distinct Unordered Pairs of elements \((a,b)\) in array A such that \(F(a) +F(b) \ge K\).
Input Format:
The first line contains 2 space separated integers N and K denoting the size of array A and the integer k from the description given above. The next line contains N space separated integers denoting the elements of array A .
Output Format:
You need to print the required answer on a single line.
Constraints:
Subtask 1: (Worth 40% of the total points):
\( 1 \le N \le 5000 \)
\( 1 \le A[i] \le 10^5 \)
\( 0 \le K \le 10^4 \)
Subtask 2: (Worth 60% of the total points) :
\( 1 \le N \le 10^6 \)
\( 1 \le A[i] \le 10^9 \)
\( 0 \le K \le 10^9 \)
Here the values of Function \(F(x)\) for all the elements of Array A from 1 to N are:
\( [7,5,5,4,3,2,0,0]\)
So, the following 5 unordered pairs are considered:
\( (1,2) \)
\( (1,3) \)
\( (1,4) \)
\( (1, 5) \)
\( (2,3) \)