B. День рождения Мотарака
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Дарк собирается посетить день рождения Мотарака. Дарк решил, что он хочет подарить Мотараку массив $$$a$$$, состоящий из $$$n$$$ неотрицательных целых чисел.

Дарк создал этот массив еще $$$1000$$$ лет назад, поэтому некоторые его элементы пропали. Дарк знает, что Мотарак не любит, когда у двух соседних элементов большая абсолютная разница. У него не так много времени, поэтому он хочет выбрать целое число $$$k$$$ ($$$0 \leq k \leq 10^{9}$$$) и заменить все пропущенные элементы в массиве $$$a$$$ числом $$$k$$$.

Обозначим за $$$m$$$ максимальную абсолютную разницу между всеми парами соседних элементов (то есть максимальное значение $$$|a_i - a_{i+1}|$$$ по всем $$$1 \leq i \leq n - 1$$$) в массиве $$$a$$$ после того, как Дарк заменит все пропавшие элементы на число $$$k$$$.

Дарк хочет выбрать число $$$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$$$, вы можете вывести любое из них.

Пример
Входные данные
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 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$$$.