SOLVE

LATER

Vanya and Array

/

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 \)

Explanation

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) \)

Time Limit:
2.0 sec(s)
for each input file.

Memory Limit:
256 MB

Source Limit:
1024 KB

Initializing Code Editor...