Dark 将参加 Motarack 的生日。 Dark 决定送给 Motarack 的礼物是一个由 $$$n$$$ 非负整数组成的数组 $$$a$$$。
Dark 在 $$$1000$$$ 年前创建了该数组,因此该数组中的一些元素消失了。 Dark 知道 Motarack 讨厌看到两个相邻元素之间的绝对差值很高的数组。他没有太多时间,所以他想选择一个整数 $$$k$$$ ($$$0 \leq k \leq 10^{9}$$$) 并用 $$$k$$$ 替换数组 $$$a$$$ 中所有缺失的元素。
设 $$$m$$$ 为 Dark 用 $$$k$$$ 替换所有缺失元素后数组 $$$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$$$ 的最小可能值和一个整数 $$$k$$$ ($$$0 \leq k \leq 10^{9}$$$),这使得数组 $$$a$$$ 中相邻元素之间的最大绝对差等于 $$$m$$$。
确保用 $$$k$$$ 替换所有缺失元素后,相邻元素之间的最大绝对差值变为 $$$m$$$。
如果有多个可能的 $$$k$$$,您可以打印其中任何一个。
示例
输入 #1
7 5 -1 10 -1 12 -1 5 -1 40 35 -1 35 6 -1 -1 9 -1 3 -1 2 -1 -1 2 0 -1 4 1 -1 3 -1 7 1 -1 7 5 2 -1 5
输出 #1
1 11 5 35 3 6 0 42 0 0 1 2 3 4
注意
在第一个测试用例中,用 $$$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$$$。