← 返回题目列表

Codeforces · 1301/B

B. 莫塔拉克的生日

中文机器翻译题面 查看原题

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$$$。