反演

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description

小鑫有一个数列a1, a2, ……,an可以交换两个相邻的数不超过k次。

 

求交换后最小的逆序对

 

Note:一个逆序对是存在一对(I, j)1 ≤ i < j ≤ n 且 a> aj 

Input

 

输入有多组,对于每组,第一行有两个数 n,k (1 ≤ n ≤ 100,000, 0 ≤ k ≤ 1,000,000,000

第二行有n个数a1,a2,…,an (0≤ai≤1,000,000,000)

Output

 

对于每一组输入,输出一个可能的最小的逆序对的数目。

Sample Input

3 1
2 2 1
3 0
2 2 1

Sample Output

1
2

Hint

 

Source