В одном небольшом городке есть мастерская, специализирующаяся на работах по дереву. Так как город маленький, в ней работают всего три резчика.
Скоро в городе планируется фестиваль деревянных игрушек. Работники мастерской хотят к нему подготовиться.
Они знают, что \(n\) человек придёт в мастерскую с просьбой сделать деревянную игрушку. Люди разные и могут хотеть разные игрушки. Для простоты обозначим паттерн игрушки, которую хочет \(i\)-й человек за \(a_i\) (\(1 \le a_i \le 10^9\)).
Каждый из резчиков может заранее выбрать какой-то паттерн \(x\) (\(1 \le x \le 10^9\)), разные резчики могут выбрать разные паттерны. \(x\) - натуральное число. За время подготовки к фестивалю резчики идеально отработают технику выполнения игрушки выбранного паттерна, что позволит им мгновенно вырезать её из дерева. Чтобы сделать игрушку паттерна \(y\) резчику, выбравшему паттерн \(x\), понадобится \(|x - y|\) времени, ведь чем больше игрушка похожа на ту, что он умеет делать мгновенно, тем быстрее резчик справится с работой.
В день фестиваля, когда очередной человек зайдёт в мастерскую с просьбой сделать деревянную игрушку, резчики могут выбрать, кто из них примется за работу. При этом резчики очень умелые люди и могут одновременно выполнять заказы для разных людей.
Так как люди не любят ждать, резчики хотят выбрать паттерны для подготовки таким образом, чтобы максимальное время ожидания среди всех людей было как можно меньше.
Выведите наилучшее максимальное время ожидания, которого смогут добиться резчики.
Выходные данные
Выведите \(t\) чисел, каждое из которых является ответом на соответствующий набор — наилучшее максимальное время ожидания, которого смогут добиться резчики.
Примечание
В первом примере входных данных резчики могут выбрать паттерны \(1\), \(7\), \(9\) для подготовки.
Во втором примере входных данных резчики могут выбрать паттерны \(3\), \(30\), \(60\) для подготовки.
Во третьем примере входных данных резчики могут выбрать паттерны \(14\), \(50\), \(85\) для подготовки.