#P1135. E.小U给你出道签到题

E.小U给你出道签到题

Description

学姐听说大家在学排序,开开心心地把以前写的博客翻出来出题,但是学姐发现自己以前写的博客看不懂了,于是她点开了自己写的机器人,问它:“小U,为什么我看不懂我的归并排序博客了?”

小U回答她:“因为有人最近忙着阴阳师打超鬼王明日方舟刷活动原神新池子fgo过剧情phigros练手速云图计划新活动完了我喘不过气来了......”

学姐担忧地问它:“那怎么办,我这周还得出题呢?”

小U告诉她:“这样,我给你不超过k次交换相邻数字的机会,你在交换后的这组数里找出最少的逆序对有多少对,如果你找的出来,我就帮你出题。”

学姐想打游戏,没法静下心来写代码,你可以帮帮她吗?(ps:不能回答不可以)

善良的学姐担心有人不知道逆序对是啥,所以悄悄告诉你,给出一个序列a1、a2、…、an,逆序对是(i,j)的个数,其中1≤i<j≤n和ai>aj。

Input

T组输入

每一组第一行包含2个整数n,k(1≤N≤10^5,0≤K≤10^9)。

第二行包含n个整数a1,a2,…,an(0≤ai≤10^9)。

Output

每一组输出最小逆序对数。

Samples

1
3 0
2 2 1
2
2
3 1
2 2 1
5 2
4 4 2 3 8
1
2

Limitation

1s, 1024KiB for each test case.