CF1858B The Walkway

在夏季信息学学校的主步道旁有 $n$ 个长椅，这些长椅按顺序编号为 $1$ 到 $n$。步道旁还有 $m$ 个卖饼干的小贩，第 $i$ 个小贩（$1 \le i \le m$）位于第 $s_i$ 个长椅旁。 Petya 站在步道的起点，他将依次经过所有长椅，从第 $1$ 个长椅走到第 $n$ 个长椅。Petya 走过相邻两个长椅之间的距离需要 $1$ 分钟。他带着一个装有无限饼干的背包。在散步过程中，Petya 会吃自己背包里的饼干，也会向小贩买饼干。 Petya 只会在长椅旁吃饼干，且遵循以下规则：他会在第 $i$ 个长椅旁（$1 \le i \le n$）吃饼干，当且仅当满足以下至少一个条件： - 第 $i$ 个长椅旁有卖饼干的小贩。此时 Petya 会向小贩买一块饼干并立即吃掉。 - Petya 还没有吃过任何饼干。此时 Petya 会从背包里拿出一块饼干并立即吃掉。 - 距离上一次吃饼干已经过去至少 $d$ 分钟。换句话说，Petya 在 $i-1, i-2, \ldots, \max(i-d+1, 1)$ 这些长椅旁都没有吃过饼干。此时 Petya 会从背包里拿出一块饼干并立即吃掉。 你可以认为 Petya 吃饼干是瞬间完成的。Petya 不会在同一个长椅旁吃两块或更多饼干。 你希望让 Petya 在散步过程中吃的饼干数量尽可能少。为此，你打算在 Petya 开始散步前，要求学校管理处移除恰好一个卖饼干的小贩。 请你计算：在移除恰好一个小贩后，Petya 最少会吃多少块饼干？又有多少个小贩，移除他们中的任意一个都能让 Petya 吃到最少数量的饼干？

第一行包含一个整数 $t$（$1 \le t \le 10^3$），表示测试用例的数量。 每个测试用例的第一行包含三个整数 $n$、$m$ 和 $d$（$2 \le d \le n \le 10^9$，$2 \le m \le \min(10^5, n)$），分别表示长椅数量、小贩数量和参数 $d$ 的值。 每个测试用例的第二行包含 $m$ 个整数 $s_1, s_2, \ldots, s_m$（$1 \le s_i \le n$），表示小贩的位置。保证 $s_{i} < s_{i+1}$ 对所有 $1 \leq i \leq m-1$ 成立。 保证所有测试用例中 $m$ 的总和不超过 $10^5$。

对于每个测试用例，输出两个整数，表示移除恰好一个小贩后，Petya 最少会吃多少块饼干，以及有多少个小贩，移除他们中的任意一个都能让 Petya 吃到最少数量的饼干。

在第一个测试用例中，$n=6$，$m=2$，$d=2$，$s=[2, 5]$。如果不移除任何小贩，Petya 会在散步过程中吃 $4$ 块饼干（注意你必须移除恰好一个小贩；此处仅为说明 Petya 吃饼干的规则）： - Petya 会在第 $1$ 个长椅旁吃一块饼干，因为他还没有吃过饼干。 - Petya 会在第 $2$ 个长椅旁吃一块饼干，因为这里有小贩。 - Petya 不会在第 $3$ 个长椅旁吃饼干，因为距离上次吃饼干只过去了 $1