Exchange

Time limit1sMemory limit256 MB

Summary

Count the swaps performed by running the first M passes of selection sort on each array.

Level: Hard8 of 10
Topics: Segment tree, Sorting, Simulation
Solved: No attempts yet

Problem

You are given an array $A$ of length $N$ and an integer $M$ . Jihak wrote the program below.

for i <- 1 to M do
    for j <- i+1 to N do
        if A[i] > A[j] then
            swap(A[i], A[j])

The array is 1-indexed, and swap(A[i], A[j]) exchanges the values of the two elements. Count how many times swap is called before the program ends.

Input

The input holds several test cases. The first line of each test case has two natural numbers $N$ and $M$ . ( $1 \le N, M \le 99999$ )

The second line has the elements $A[1], A[2], \dots, A[N]$ of the array $A$ , separated by spaces. ( $-10^9 \le A[i] \le 10^9$ )

The input runs to the end of the file and holds at most 20 test cases.

Output

For each test case, print the number of swap calls on one line.

Examples3

Example 1
Input
```
3 3
2 1 3
4 1
3 2 -1 -10
```
Expected output
```
1
3
```
Example 2
Input
```
5 5
1 2 3 4 5
```
Expected output
```
0
```
Example 3
Input
```
6 6
6 5 4 3 2 1
```
Expected output
```
15
```