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

    Type: Default 1000ms 256MiB

E.小U给你出道签到题

You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

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.

2022新生训练第一周

Not Claimed
Status
Done
Problem
9
Open Since
2022-11-9 0:00
Deadline
2022-11-19 23:59
Extension
24 hour(s)