3533. Bookface

【题目描述】

承担一个雄心勃勃的项目？检查。日夜不知疲倦地工作，在最后期限前完成任务？检查。每天以小块的形式提交代码？检查。在所有这些工作之后，你，最有野心的到目前为止，Bookface的软件开发人员认为你和你的晋升之间没有任何障碍。你完全错了。

在把你的晋升计划发给管理层之前，你决定让你的同事小弗朗牛接受看一眼。一眼就能看出问题所在。“在书面，你必须行动迅速”–弗兰纽说–“快速行动，改变现状。你不可能是可预测的和船舶同样大小的承诺，每天这样！”.

您查看了在项目的n天中每一天添加的行数，并意识到Franiu是有道理的。如果我们用ci表示第i天的计数，然后所有的ci值都变得相对接近。幸运的是，您的朋友也知道如何解决这个问题—您只需重写提交历史记录即可看起来好多了！

与Franiu一起，您选择了一个值d，并决定将| ci−cj |≥d保留为任何1≤i<j≤n。为此，您可以选择一天，并在该天的提交中添加或删除一行代码一天。您可以执行任意多个这样的操作，每个操作都需要1秒。你需要多少时间完成你的目标？当然，提交中的代码行数必须始终保持非负数。

看不懂的话看原题面吧！C题！

https://codeforces.com/gym/102576/attachments/download/10799/200202.pdf

【输入格式】

第一行输入包含测试用例数T（1≤T≤100000）。测试用例的描述跟随。 每个测试用例的第一行包含项目n（1≤n≤200000）的天数和所选的常数d（1≤d≤10^6). 第二行包含n个数字ci（0≤ci≤3·10^11）–代码行数在第i天添加。 所有测试用例中的总天数不超过10^6天.

【输出格式】

输出T行数表示每组数据的答案。

【样例输入】

2
4 1
0 0 0 0
4 10
1 100 5 10

【样例输出】

6
16

【来源】

38th Petrozavodsk Programming Camp, Winter 2020 Day 5: Jagiellonian U Contest, Sunday, February 2, 2020