Inversion

Time Limit
1s
Memory Limit
131072KB
Judge Program
Standard
Ratio(Solve/Submit)
23.81%(5/21)
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.

Sample Input:
3 1
2 2 1
3 0
2 2 1
Sample Output:
1
2

Submit