Time Limit

1s

Memory Limit

131072KB

Judge Program

Standard

Ratio(Solve/Submit)

15.00%(3/20)

Description:

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}.

Input:

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}).

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