CF1301B Motarack's Birthday

Dark 要去参加 Motarack 的生日派对。他决定送给 Motarack 一份礼物，这份礼物是一个包含 $n$ 个非负整数的数组 $a$。 Dark 在 $1000$ 年前就已经创建好了这个数组，所以其中有些元素已经消失了。Dark 知道 Motarack 非常讨厌看到数组中有两个相邻元素的绝对差值过大。他时间紧迫，所以他想选择一个整数 $k$（$0 \leq k \leq 10^{9}$），并用 $k$ 替换数组 $a$ 中所有缺失的元素。 设 $m$ 为替换后数组 $a$ 中所有相邻元素的最大绝对差值（即所有 $1 \leq i \leq n-1$ 的 $|a_i - a_{i+1}|$ 的最大值）。 Dark 应该选择一个整数 $k$，使得 $m$ 最小。你能帮帮他吗？

输入包含多组测试用例。第一行包含一个整数 $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$。

对于每个测试用例，输出两整数，分别为 $m$ 的最小可能值，以及使得相邻元素最大绝对差值等于 $m$ 的整数 $k$（$0 \leq k \leq 10^9$）。 确保在用 $k$ 替换所有缺失元素后，相邻元素的最大绝对差值等于 $m$。 如果有多个 $k$ 满足条件，可以输出任意一个。

在第一个测试用例中，将所有缺失元素替换为 $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$。 由 ChatGPT 4.1 翻译