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