RoAlgo Contest #11 - Back to School 2024 | Remove Inversions

Task

You are given an array $A$ of $N$ elements. We define an inversion as a pair of indices $(i, j)$ where $1 \leq i < j \leq N$ and $A_i > A_j$.

An operation is defined as the removal of an element.

You need to print the number of ways to perform a maximum of 2 operations such that the remaining array has exactly $K$ inversions.

Input data

The first line of input contains two numbers, $N$ and $K$. These represent the number of elements in the array and the desired number of inversions after performing the operations, respectively. The second line contains $N$ elements representing the array $A$.

Output data

Print the total number of ways to remove elements.

Constraints and clarifications

• $1 \leq N \leq 2 \cdot 10^5$
• $0 \leq K \leq \frac{N \cdot (N - 1)}{2}$
• $1 \leq A_i \leq 2 \cdot 10^5$, for $1 \leq i \leq N$

Subtasks

• For 15 points, $1 \leq N \leq 200$.
• For another 20 points, $201 \leq N \leq 10^4$.
• For another 20 points, $10^4 \leq N \leq 2 \cdot 10^5$ şi $1 \leq A_i \leq 26$.
• For another 45 points, $10^4+1 \leq N \leq 2 \cdot 10^5$.

Example 1

stdin

6 2
1 5 2 3 4 1

stdout

6

Explanation

The $6$ ways to remove two elements are: $[2,3]$, $[2,4]$, $[2,5]$, $[3,6]$, $[4,6]$, $[5,6]$.

Example 2

stdin

8 16
1 5 4 5 2 1 1 1

stdout

2

Explanation

The two ways are either not to remove any element or to remove the first element.