Субботник
(Время: 1 сек. Память: 16 Мб Сложность: 44%)
В этом году Иван Иванович решил отметить приход осени субботником, чтобы убрать весь мусор во дворе дома номер 31 по улице Осенней. На субботник он пригласил N знакомых старушек, живущих в том же самом доме. Однако, в самом начале мероприятия выяснилось, что по одиночке старушки работают плохо, так как им хочется во время работы еще и поговорить друг с другом.
Иван Иванович подумал и принял волевое решение разбить старушек на группы так, чтобы в каждой группе было не менее 2 старушек. Старушки отличаются друг от друга уровнем разговорчивости, и если в одну группу попадут две старушки, у одной из которых маленький уровень разговорчивости, а у второй - большой, то они не могут поговорить друг с другом и работа будет стопориться.
Назовем разговорчивостью группы разность между максимальным и минимальным уровнями разговорчивости старушек в группе. Например, если уровни разговорчивости старушек в группе равны 7, 3 и 11, то разговорчивость группы равна 11 - 3 = 8. Разговорчивостью разбиения старушек на группы назовем максимальную из разговорчивостей групп, входящих в разбиение.
Требуется написать программу, которая поможет Ивану Ивановичу найти разбиение старушек на группы, разговорчивость которого минимальна.
Входные данные
Входной файл INPUT.TXT содержит в первой строке число N (2 ≤ N ≤ 1000) – количество старушек. Во второй строке записано N чисел от 1 до 109 – разговорчивости старушек.
Выходные данные
Выходной текстовый файл OUTPUT.TXT должен содержать одно целое число, равное минимально возможной разговорчивости разбиения старушек на группы.
Примеры
| № | INPUT.TXT | OUTPUT.TXT |
|---|
| 1 | 2
1 1000000000 | 999999999 |
| 2 | 3
1 2 3 | 2 |
| 3 | 8
1 10 100 1000 1000 100 10 1 | 0 |
| 4 | 10
258 740 156 244 458 680 390 694 844 817 | 102 |
Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!
| 
