P13631 [NWRRC 2021] Day Streak

最近，著名的竞赛编程网站 Deltaforces 在用户资料中增加了许多新的可视化信息。特别地，新增了“最大连续天数”——即连续若干天每天至少解决一道题的最大天数。你觉得你资料中的最大连续天数并不能准确反映你的训练努力。因此，你产生了一个想法——如果你可以更改资料中的时区，是否能提升你的最大连续天数？ 我们将这个设定形式化如下。假设你总共解决了 $n$ 道题，第 $i$ 道题是在时间 $a_i$ 被解决的。共有 $m$ 个时区，编号从 $0$ 到 $m-1$。默认时区为 $0$。如果你选择将时区更改为 $t$，那么所有题目的时间戳都会增加 $t$：即第 $i$ 道题的时间变为 $a_i + t$，对所有 $i$ 都成立。 在时间 $x$ 解决的问题被认为是在第 $\lfloor \frac{x}{m} \rfloor$ 天解决的。这里 $\lfloor v \rfloor$ 表示不超过 $v$ 的最大整数。 为了展示最大连续天数，Deltaforces 会找到一组 $l$ 和 $r$，使得你在第 $l, l+1, \ldots, r$ 天中每天至少解决了一道题，并且 $r-l+1$ 尽可能大。此时你的最大连续天数就是 $r-l+1$。 请你通过选择一个合适的时区，使你的最大连续天数最大，并输出最大连续天数以及对应的时区。

每个测试点包含多组测试数据。第一行包含测试用例数 $t$（$1 \le t \le 2 \cdot 10^5$）。接下来是每组测试数据的描述。 每组测试数据的第一行包含两个整数 $n$ 和 $m$，分别表示你解决的问题数和时区数（$1 \le n \le 2 \cdot 10^5$，$1 \le m \le 10^9$）。第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$，表示你解决每道题的时间戳，且时间戳各不相同，按时间递增排列（$0 \le a_1 < a_2 < \dotsb < a_n \le 10^9$）。 保证所有测试用例中 $n$ 的总和不超过 $2 \cdot 10^5$。

对于每组测试数据，输出两个整数 $s$ 和 $t$，分别表示最大连续天数和实现该天数的任意一个时区（$1 \le s \le n$，$0 \le t < m$）。

在第一个样例测试中，当你选择时区 $2$ 时，你的题目时间戳变为 $2$、$5$、$10$ 和 $26$。这意味着这些题目分别被认为是在第 $0$、$0$、$1$ 和 $2$ 天解决的，也就是一个 $3$ 天的连续天数。时区 $3$、$4$ 和 $5$ 也能得到相同的答案。 在第二个样例测试中，选择时区 $5$ 后，你的题目时间戳变为 $37$ 和 $40$，对应第 $3$ 天和第 $4$ 天。时区 $6$ 和 $7$ 也可以。 在第三个样例测试中，只有一个时区，你的最大连续天数就是 $5$。 在第四个样例测试中，你在很短的时间内解决了很多题，但最大连续天数也只能是 $2$。 由 ChatGPT 4.1 翻译