Межзвёздная торговля
В качестве редкой награды за прохождение одного из его загадочных испытаний, Q предложил командиру Сиско возможность переместить оба конца Баджорской червоточины (и, конечно, вместе с ней и станцию Deep Space Nine). Командир запросил предложения по перемещению, и различные торговцы хотят переместить концы в известное пространство, чтобы сократить время транзита между планетами, известными своей торговлей. Ваша задача — выяснить, как разместить концы червоточины так, чтобы минимизировать максимальное расстояние между любой парой этих планет.
Удобно, что все интересующие планеты лежат на прямой линии, и при отсутствии червоточины расстояние между любой парой из них просто равно расстоянию по прямой. Как только червоточина добавлена, путешественник имеет дополнительную возможность перемещаться от одной планеты прямо к одному концу червоточины, а затем прямо от другого конца червоточины к другой планете. Пройденное расстояние в этом случае равно сумме этих двух расстояний (путешествие между двумя концами червоточины происходит мгновенно). Заметьте, что путешественник всегда имеет возможность не использовать червоточину, даже если конец червоточины находится прямо между двумя интересующими планетами. Наконец, вы можете разместить конец червоточины произвольно близко к любой планете, так что расстояние от планеты до червоточины фактически равно нулю.
Входные данные
Ввод начинается с строки с одним целым числом T (1 ≤ T ≤ 50), обозначающим количество тестовых случаев. Каждый тестовый случай начинается с строки с одним целым числом N (2 ≤ N ≤ 4000), обозначающим количество планет. Далее следуют N строк, каждая с одним целым числом x_i (-10^9 ≤ x_i ≤ 10^9), обозначающим расположение планеты i (все планеты являются точками на x-оси). Ни две планеты не будут находиться в одном и том же месте.
Выходные данные
Для каждого тестового случая выведите в одной строке максимальное расстояние между любой парой планет после того, как червоточина будет размещена таким образом, чтобы минимизировать это значение. Если это расстояние дробное, округлите его до следующего целого числа. Обратите внимание, что хотя все координаты планет заданы целыми числами, координаты червоточины могут не быть целыми.