#P18600. Investors

Investors

Investors

2087 年,人工智能已经解决了那些甚至还没有被提出的超图染色问题,而建成后的 Hyperloop 网络却成了世界上最慢的地铁。

为了安抚投资者,Melon Usk 决定展示公司的财务结果。公司的收入可以表示为一个长度为 nn 的整数序列,第 ii 个数表示第 ii 个月的收入。由于票务收入不高、咖啡采购成本又很大,这些数字并不好看,于是 Usk 想稍微“调整”一下。

一次调整可以选择序列中的一个连续区间,将其中每个数都增加同一个正整数。他最多可以进行 kk 次这样的操作;不同次操作所增加的数可以不同,没有给定的上界。

投资者希望收入增长,不喜欢收入下降。请帮助 Usk,使最终序列的逆序对数量最少。

这里,逆序对是满足 i<ji<j 且 ai>aja_i>a_j 的一对下标 (i,j)(i,j)。相等的两个数不构成逆序对。

输入格式

第一行一个整数 zz,表示测试用例数。

每个测试用例第一行两个整数 n,kn,k。第二行 nn 个整数 a1,a2,…,ana_1,a_2,\ldots,a_n。

输出格式

对每个测试用例输出一行一个整数,表示最多进行 kk 次连续区间加正整数操作后,最少可能剩下的逆序对数量。

数据范围

  • 1≤z≤4001\le z\le400;
  • 1≤n≤60001\le n\le6000,0≤k≤n0\le k\le n;
  • 0≤ai≤1090\le a_i\le10^9;
  • 所有测试用例的 nn 之和不超过 60006000。

样例输入 1

2
6 1
4 5 6 2 2 1
6 2
4 5 6 2 2 1

样例输出 1

2
0