bobo has a sequence a
1,a
2,…,a
n. He is allowed to swap two
adjacent numbers for no more than k times.
Find the minimum number of inversions after his swaps.
Note: The number of inversions is the number of pair (i,j) where 1≤i<j≤n and a
i>a
j.
The input consists of several tests. For each tests:
The first line contains 2 integers n,k (1≤n≤10
5,0≤k≤10
9). The second line contains n integers a
1,a
2,…,a
n (0≤a
i≤10
9).
For each tests:
A single integer denotes the minimum number of inversions.