嗷呜嗷呜事务所II

题目描述

Orange的正在带领一支由 $n$ 只奇美拉构成的小队外出完成任务。每只奇美拉都会有一个疲劳值，每完成一个任务之后，所有奇美拉的疲劳值都会增加 $1$。此外，Orange明白，奇美拉并不是超人，不能一直工作，当一只奇美拉的疲劳值到达阈值 $L$ 时，他就会安排这只奇美拉进行休息，休息之后，这只奇美拉的疲劳值则会清零。最开始，每只奇美拉的疲劳值为 $a_i$。

当然，尽管Orange的管理非常人性化(bushi)，每只奇美拉任然会产生不满。对于某一时刻的某只奇美拉而言，它的前方(方向如下图所示)每存在一只疲劳值比它低的奇美拉，它就会产生一点怨气。而当团队中所有奇美拉的怨气之和过高时，所有的奇美拉就会罢工。 为了防止奇美拉们罢工，Orange想知道，在执行多少个任务之后，奇美拉们的怨气之和会达到最大值。

你的任务是，求出奇美拉们的怨气之和的最大值以及最少完成多少个任务后会首次达到这个最大值。

形式化的说，你需要求出一个整数 $k$，最大化如下函数的值：

$$f(k)=\sum_{i=1}^n \sum_{j=i}^n [((a_i + k) \bmod L) > ((a_j + k) \bmod L)]$$

在数学中，$[\text{condition}]$ 表示条件数，当 $\text{condition}$ 为真时，表达式值为 $1$，否则为 $0$。

输入格式

输入包含多组测试数据。 第一行为一个测试数据数 $T$。 对于每组测试数据： 第一行为2个整数 $n,L$，表示奇美拉的数量和一只奇美拉的疲劳值阈值。 接下来一行包含 $n$ 个整数 $a_i$，表示每只奇美拉最开始的疲劳值。

数据范围

$1 \le n \le 3\times 10^5$ $1 \le L \le 10^9$ $\sum n \le 10^6$

输出格式

对于每组测试数据，输出一个整数，表示答案。

样例 #1

样例输入 #1

2
5 10
3 7 2 3 0
5 10
7 8 9 6 9

样例输出 #1

7 0
7 1

提示

样例解释1

最开始工作时，第一只奇美拉会产生 $2$ 点怨气，第二只会产生 $3$ 点怨气，第三只会产生 $1$ 点怨气，第四只会产生 $1$ 点怨气，此时奇美拉们的怨气之和为 $7$。可以证明这是能达到的怨气之和的最大值。

样例解释2

最开始工作时，第一只奇美拉会产生 $1$ 点怨气，第二只会产生 $1$ 点怨气，第三只会产生 $1$ 点怨气，此时奇美拉们的怨气之和 $3$。

在第一次工作后，奇美拉们的疲劳值变为 $[8, 9, 0, 7, 0]$，第一只奇美拉会产生 $3$ 点怨气，第二只会产生 $3$ 点怨气，第四只会产生 $1$ 点怨气此时怨气之和为 $7$,可以证明这是能达到的怨气之和的最大值。