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