#P18600. Investors
Investors
Investors
2087 年,人工智能已经解决了那些甚至还没有被提出的超图染色问题,而建成后的 Hyperloop 网络却成了世界上最慢的地铁。
为了安抚投资者,Melon Usk 决定展示公司的财务结果。公司的收入可以表示为一个长度为 的整数序列,第 个数表示第 个月的收入。由于票务收入不高、咖啡采购成本又很大,这些数字并不好看,于是 Usk 想稍微“调整”一下。
一次调整可以选择序列中的一个连续区间,将其中每个数都增加同一个正整数。他最多可以进行 次这样的操作;不同次操作所增加的数可以不同,没有给定的上界。
投资者希望收入增长,不喜欢收入下降。请帮助 Usk,使最终序列的逆序对数量最少。
这里,逆序对是满足 且 的一对下标 。相等的两个数不构成逆序对。
输入格式
第一行一个整数 ,表示测试用例数。
每个测试用例第一行两个整数 。第二行 个整数 。
输出格式
对每个测试用例输出一行一个整数,表示最多进行 次连续区间加正整数操作后,最少可能剩下的逆序对数量。
数据范围
- ;
- ,;
- ;
- 所有测试用例的 之和不超过 。
样例输入 1
2
6 1
4 5 6 2 2 1
6 2
4 5 6 2 2 1
样例输出 1
2
0