Inversion
Description:
bobo has a sequence a1,a2,…,an. 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 ai>aj.
Input:
The input consists of several tests. For each tests:
The first line contains 2 integers n,k (1≤n≤105,0≤k≤109). The second line contains n integers a1,a2,…,an (0≤ai≤109).
Output:
For each tests:
A single integer denotes the minimum number of inversions.
A single integer denotes the minimum number of inversions.
Sample Input:
3 1 2 2 1 3 0 2 2 1
Sample Output:
1 2
Submit