CF1858B.The Walkway

There are $n$ benches near the Main Walkway in Summer Infomatics School. These benches are numbered by integers from $1$ to $n$ in order they follow. Also there are $m$ cookie sellers near the Walkway. The $i$-th ($1 \le i \le m$) cookie sellers is located near the $s_i$-th bench.

Petya is standing in the beginning of the Walkway. He will pass near all benches starting from the $1$-st bench and ending with the $n$-th bench. Petya passes the distance between two consecutive benches in $1$ minute. He has a knapsack with an infinite amount of cookies. Petya is going to eat cookies from his knapsack and buy them from cookie sellers during the walk.

Petya eats cookies only near the benches according to the following rule: he will eat the cookie near the $i$-th ($1 \le i \le n$) bench if and only if at least one of the following conditions holds:

• There is a cookie seller near the $i$-th bench. Then Petya will buy a cookie from cookie seller and eat it immediately.
• Petya has not yet eaten a cookie. Then Petya will take a cookie from his knapsack and eat it immediately.
• At least $d$ minutes passed since Petya ate the previous cookie. In other words, Petya has not eaten a cookie near the benches $i-1, i-2, \ldots, \max(i-d+1, 1)$. Then Petya will take a cookie from his knapsack and eat it immediately.

You may assume that Petya eats cookies instantly. Petya will not eat two or more cookies near the same bench.

You want to minimize the number of cookies Petya will eat during his walk. In order to do this, you will ask the administration of the Summer Informatics School to remove exactly one cookie seller from the Walkway before Petya starts his walk.

Please determine the minimum possible number of cookies Petya can eat after removing exactly one cookie seller. Also determine the number of cookie sellers, such that if you remove one of them, Petya will eat the minimum possible number of cookies.

Summer 信息学学校主步道旁有 $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 在整个行走过程中所食用的饼干总数。为此，你将请求 Summer 信息学学校管理部门在 Petya 开始行走前恰好移除一位饼干售卖者。

请确定：在恰好移除一位饼干售卖者后，Petya 所能食用的饼干数的最小可能值；同时确定，有多少位饼干售卖者满足：若移除其中任意一位，Petya 食用的饼干数即达到该最小可能值。

The first line contains a single integer $t$ ($1 \le t \le 10^3$) — the number of test cases.

The first line of each test case contains three integers $n$, $m$ and $d$ ($2 \le d \le n \le 10^9$, $2 \le m \le \min(10^{5}, n)$) — the number of benches, the number of cookie sellers and the value of parameter $d$ from the statement, respectively.

The second line of each test case contains $m$ integers $s_1, s_2, \ldots, s_m$ ($1 \le s_i \le n$) — the locations of the cookie sellers. It is guaranteed that $s_{i} \lt s_{i+1}$ for all $1 \leq i \leq m - 1$.

It is guaranteed that the sum of $m$ over all test cases does not exceed $10^5$.

第一行包含一个整数 $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$）—— 表示各饼干卖家的位置。保证对所有 $1 \leq i \leq m - 1$ 均有 $s_{i} \lt s_{i+1}$。

保证所有测试用例中 $m$ 的总和不超过 $10^5$。

For each test case print two integers — the minimum number of cookies that Petya can eat if exactly one cookie seller is removed, and the number of cookie sellers such that if one of them is removed, Petya will eat the minimum possible number of cookies.

对于每个测试用例，输出两个整数：恰好移除一名饼干销售员时，Petya 能吃的最少饼干数量；以及满足“移除该销售员后 Petya 吃到的饼干数量达到最小值”的饼干销售员的数量。

In the first test case $n=6$, $m=2$, $d=2$ and $s=[2, 5]$. If no cookie seller is removed, then Petya will eat $4$ cookies during his walk (note that you have to remove exactly one cookie seller; this case is explained only to show how Petya decides whether to eat a cookie):

• Petya will eat a cookie near the $1$-st bench since he has not yet eaten a cookie.
• Petya will eat a cookie near the $2$-nd bench since there is a cookie seller near this bench.
• Petya will not eat a cookie near the $3$-rd bench since only $1 \lt d$ minute passed since he ate a cookie.
• Petya will eat a cookie near the $4$-th bench since $2\ge d$ minutes passed since he ate a cookie.
• Petya will eat a cookie near the $5$-th bench since there is a cookie seller near this bench.
• Petya will not eat a cookie near the $6$-th bench since only $1 \lt d$ minute passed since he ate a cookie.

If the $1$-st cookie seller is removed, Petya will eat $3$ cookies (near the benches $1$, $3$ and $5$). If the $2$-nd cookie seller is removed, Petya will eat $4$ cookies (near the benches $1$, $2$, $4$ and $6$).

Thus, the minimum number of cookies Petya will eat is $3$; there is only one cookie seller such that removing it results in minimizing the number of cookies Petya will eat.

In the second test case

• the removal of the $1$-st or the $2$-nd cookie seller results in Petya eating $5$ cookies near the benches $1$, $3$, $5$, $7$, $8$;
• the removal of the $3$-rd cookie seller results in Petya eating $4$ cookies near the benches $1$, $3$, $5$, $7$.

Note that the second integer you should output is the number of (that is, amount) cookie sellers, not the index of a cookie seller to remove. Thus, the answer to the second test case is 4 1 because there is only one cookie seller such that removing it results in Petya eating four cookies, which is the minimum possible.

In the third test case Petya will eat $4$ cookies no matter what cookie seller is removed.

Note that Petya is not interested in minimizing the number of cookies he will eat, so he eats cookies whenever it is possible under the rule from the statement.

在第一个测试用例中，$n=6$，$m=2$，$d=2$，且 $s=[2, 5]$。若不移除任何卖饼干的小贩，则佩蒂亚在散步过程中将吃掉 $4$ 块饼干（注意：你必须恰好移除一名卖饼干的小贩；此处仅用于说明佩蒂亚如何决定是否吃饼干）：

• 佩蒂亚将在第 $1$ 条长椅旁吃一块饼干，因为这是他第一次吃饼干；
• 佩蒂亚将在第 $2$ 条长椅旁吃一块饼干，因为该长椅旁有一名卖饼干的小贩；
• 佩蒂亚不会在第 $3$ 条长椅旁吃饼干，因为距离上一次吃饼干仅过去 $1 < d$ 分钟；
• 佩蒂亚将在第 $4$ 条长椅旁吃一块饼干，因为距离上一次吃饼干已过去 $2 \ge d$ 分钟；
• 佩蒂亚将在第 $5$ 条长椅旁吃一块饼干，因为该长椅旁有一名卖饼干的小贩；
• 佩蒂亚不会在第 $6$ 条长椅旁吃饼干，因为距离上一次吃饼干仅过去 $1 < d$ 分钟。

若移除第 $1$ 名卖饼干的小贩，则佩蒂亚将吃掉 $3$ 块饼干（分别在第 $1$、$3$、$5$ 条长椅旁）；若移除第 $2$ 名卖饼干的小贩，则佩蒂亚将吃掉 $4$ 块饼干（分别在第 $1$、$2$、$4$、$6$ 条长椅旁）。

因此，佩蒂亚将吃的最少饼干数为 $3$；仅存在一名卖饼干的小贩，移除它可使佩蒂亚吃的饼干数达到最小值。

在第二个测试用例中：

• 移除第 $1$ 名或第 $2$ 名卖饼干的小贩，均导致佩蒂亚在第 $1$、$3$、$5$、$7$、$8$ 条长椅旁吃掉 $5$ 块饼干；
• 移除第 $3$ 名卖饼干的小贩，导致佩蒂亚在第 $1$、$3$、$5$、$7$ 条长椅旁吃掉 $4$ 块饼干。

注意：你需要输出的第二个整数表示满足条件的卖饼干小贩的数量（即有多少名小贩，移除其中任意一名均可使佩蒂亚吃的饼干数达到最小值），而非要移除的小贩的编号。因此，第二个测试用例的答案是 4 1，因为仅存在一名卖饼干的小贩，移除它可使佩蒂亚吃掉 $4$ 块饼干，这是可能的最小值。

在第三个测试用例中，无论移除哪一名卖饼干的小贩，佩蒂亚都将吃掉 $4$ 块饼干。

注意：佩蒂亚并不主动追求吃最少的饼干数，他只是严格遵守题面所述规则，在允许的情况下总是吃饼干。