Codeforces Round 619 (Div. 2) |
---|
Закончено |
Дарк собирается посетить день рождения Мотарака. Дарк решил, что он хочет подарить Мотараку массив $$$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]$$$.
Поэтому максимальная абсолютная разница между всеми парами соседних элементов будет равна $$$3$$$.
Название |
---|