CF1301B.Motarack's Birthday

Dark is going to attend Motarack's birthday. Dark decided that the gift he is going to give to Motarack is an array $a$ of $n$ non-negative integers.

Dark created that array $1000$ years ago, so some elements in that array disappeared. Dark knows that Motarack hates to see an array that has two adjacent elements with a high absolute difference between them. He doesn't have much time so he wants to choose an integer $k$ ($0 \leq k \leq 10^{9}$) and replaces all missing elements in the array $a$ with $k$.

Let $m$ be the maximum absolute difference between all adjacent elements (i.e. the maximum value of $|a_i - a_{i+1}|$ for all $1 \leq i \leq n - 1$) in the array $a$ after Dark replaces all missing elements with $k$.

Dark should choose an integer $k$ so that $m$ is minimized. Can you help him?

Dark 将要参加 Motarack 的生日聚会。Dark 决定送给 Motarack 的礼物是一个长度为 $n$ 的非负整数数组 $a$。

Dark 在 1000 年前创建了该数组，因此其中部分元素已经丢失。Dark 知道 Motarack 非常讨厌看到相邻元素之间绝对差值过大的数组。由于时间紧迫，他希望选择一个整数 $k$（满足 $0 \leq k \leq 10^{9}$），并将数组 $a$ 中所有缺失的元素全部替换为 $k$。

令 $m$ 表示将所有缺失元素替换为 $k$ 后，数组 $a$ 中所有相邻元素之间的最大绝对差值（即对所有 $1 \leq i \leq n - 1$，$|a_i - a_{i+1}|$ 的最大值）。

Dark 应当选择一个整数 $k$，使得 $m$ 尽可能小。你能帮他实现吗？

The input consists of multiple test cases. The first line contains a single integer $t$ ($1 \leq t \leq 10^4$) — the number of test cases. The description of the test cases follows.

The first line of each test case contains one integer $n$ ($2 \leq n \leq 10^{5}$) — the size of the array $a$.

The second line of each test case contains $n$ integers $a_1, a_2, \ldots, a_n$ ($-1 \leq a_i \leq 10 ^ {9}$). If $a_i = -1$, then the $i$-th integer is missing. It is guaranteed that at least one integer is missing in every test case.

It is guaranteed, that the sum of $n$ for all test cases does not exceed $4 \cdot 10 ^ {5}$.

输入包含多个测试用例。第一行包含一个整数 $t$（$1 \leq t \leq 10^4$），表示测试用例的数量。随后是各测试用例的描述。

每个测试用例的第一行包含一个整数 $n$（$2 \leq n \leq 10^{5}$），表示数组 $a$ 的大小。

每个测试用例的第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$-1 \leq a_i \leq 10 ^ {9}$）。若 $a_i = -1$，则表示第 $i$ 个整数缺失。保证每个测试用例中至少有一个整数缺失。

保证所有测试用例的 $n$ 之和不超过 $4 \cdot 10 ^ {5}$。

Print the answers for each test case in the following format:

You should print two integers, the minimum possible value of $m$ and an integer $k$ ($0 \leq k \leq 10^{9}$) that makes the maximum absolute difference between adjacent elements in the array $a$ equal to $m$.

Make sure that after replacing all the missing elements with $k$, the maximum absolute difference between adjacent elements becomes $m$.

If there is more than one possible $k$, you can print any of them.

以如下格式输出每个测试用例的答案：

您应输出两个整数：$m$ 的最小可能值，以及一个整数 $k$（$0 \leq k \leq 10^{9}$），使得数组 $a$ 中相邻元素间的最大绝对差值等于 $m$。

请确保在将所有缺失元素替换为 $k$ 后，相邻元素间的最大绝对差值恰好为 $m$。

若存在多个可能的 $k$，您可以输出其中任意一个。

In the first test case after replacing all missing elements with $11$ the array becomes $[11, 10, 11, 12, 11]$. The absolute difference between any adjacent elements is $1$. It is impossible to choose a value of $k$, such that the absolute difference between any adjacent element will be $\leq 0$. So, the answer is $1$.

In the third test case after replacing all missing elements with $6$ the array becomes $[6, 6, 9, 6, 3, 6]$.

• $|a_1 - a_2| = |6 - 6| = 0$;
• $|a_2 - a_3| = |6 - 9| = 3$;
• $|a_3 - a_4| = |9 - 6| = 3$;
• $|a_4 - a_5| = |6 - 3| = 3$;
• $|a_5 - a_6| = |3 - 6| = 3$.

So, the maximum difference between any adjacent elements is $3$.

在第一个测试用例中，将所有缺失元素替换为 $11$ 后，数组变为 $[11, 10, 11, 12, 11]$。任意相邻元素之间的绝对差值均为 $1$。不存在某个 $k$ 的取值，使得任意相邻元素之间的绝对差值 $\leq 0$。因此，答案为 $1$。

在第三个测试用例中，将所有缺失元素替换为 $6$ 后，数组变为 $[6, 6, 9, 6, 3, 6]$。

• $|a_1 - a_2| = |6 - 6| = 0$；
• $|a_2 - a_3| = |6 - 9| = 3$；
• $|a_3 - a_4| = |9 - 6| = 3$；
• $|a_4 - a_5| = |6 - 3| = 3$；
• $|a_5 - a_6| = |3 - 6| = 3$。

因此，任意相邻元素之间的最大差值为 $3$。