Дарк собирается посетить день рождения Мотарака. Дарк решил, что он хочет подарить Мотараку массив \(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\) будет минимально. Можете ли вы помочь ему?
Выходные данные
Выведите ответы для каждого тестового случая в следующем формате:
Вы должны вывести два целых числа, минимальное возможное значение \(m\) и целое число \(k\) (\(0 \leq k \leq 10^{9}\)), которое делает максимальную абсолютную разницу между соседними элементами массива \(a\) равной \(m\).
Обратите внимание, что после замены всех пропавших элементов на \(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\).
Примеры
| № | Входные данные | Выходные данные |
|
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 11
5 35
3 6
0 42
0 0
1 2
3 4
|