Аркадий Аркадьевич, широко известный в узких кругах инженер, после выхода на пенсию решил отдохнуть и заняться садоводством. Он уже купил себе участок и собирается сажать там различные овощи и фрукты. Но всем известно, что растения должны расти в грядках, поэтому сейчас Аркадий Аркадьевич занят их сооружением.
Для того чтобы собрать прямоугольную грядку, нужны 4 доски. В идеале это должны быть две пары досок равной длины, тогда из них можно сложить ровный прямоугольник. Но если доски имеют неравную длину, то в одном из углов полученной грядки можно разместить пластиковый уголок: две планки длины $$$r$$$, скреплённые под прямым углом. Уголок со стороной $$$r$$$ позволит увеличить длины двух досок на величину, не превосходящую $$$r$$$. Если противоположными сторонами грядки будут доски длины $$$a$$$ и $$$b$$$, а также $$$c$$$ и $$$d$$$ соответственно, то для того чтобы сделать прямоугольную грядку из этих досок, понадобится уголок размера $$$\max(|a-b|, |c-d|)$$$ . Например, чтобы сделать грядку из досок длины 5, 7, 3, 2, понадобится уголок размера 2. На рисунке чёрным цветом изображены доски и красным цветом изображён уголок.
В сарае у Аркадия Аркадьевича нашлись $$$n$$$ досок, $$$i$$$-я из которых имеет длину $$$l_i$$$. Теперь он хочет выбрать из них четыре и сложить из них грядку таким образом, чтобы использовать уголок наименьшего размера. Помогите ему.
Первая строка входных данных содержит число $$$n$$$ ($$$4 \leq n \leq 10^5$$$) — количество досок в сарае у Аркадия Аркадьевича.
Следующие $$$n$$$ строк содержат числа $$$l_1, \dots, l_n$$$ ($$$1 \leq l_i \leq 10^9$$$) — длины досок.
Программа должна сначала вывести число $$$r$$$ — минимально возможный размер уголка.
Во второй строке выведите 4 числа $$$a$$$, $$$b$$$, $$$c$$$, $$$d$$$ — длины досок, которые необходимо выбрать для грядки. При этом противоположными сторонами прямоугольника будут доски $$$a$$$ и $$$b$$$, а также $$$c$$$ и $$$d$$$. Если есть разные варианты выбора досок для грядки с одной и той же величиной уголка, можно вывести любой из них.
Решения, правильно работающие, когда $$$n \leq 30$$$, будут оцениваться в 20 баллов.
Решения, правильно работающие, когда $$$n \leq 100$$$, будут оцениваться в 45 баллов.
Решения, правильно работающие, когда $$$n \leq 500$$$, будут оцениваться в 65 баллов.
Решения, правильно работающие, когда все $$$l_i \leq 30$$$, будут оцениваться в 10 баллов.
65912372
2 2 3 5 7
6173638
1 3 3 6 7
