ДАЮ 35 поинтов УМОЛЯЮ посчитайте СДАЮ ЧЕРЕЗ ЧАСB. Справедливое распределение подарковограничение по времени на тест1 секундаограничение по памяти на тест256 мегабайтвводстандартный вводвыводстандартный выводДед Мороз подарил семиклассникам на новогоднем вечере большой мешок подарков. В классе учатся n детей. Когда открыли мешок, оказалось, что в нем находятся n+1 наборов конфет в различных красивых упаковках. Увидев, что на дне каждой упаковки указано количество конфет в наборе, дети выяснили, что в i-ом наборе находится ai конфет. Дед Мороз попросил детей распределить наборы между собой одним из двух способов:Один из детей получает два набора, остальные n−1 детей — по одному набору. Все n детей получают по одному набору, оставшийся набор возвращается Деду Морозу. Дети хотят распределить между собой эти наборы наиболее справедливым образом, считая несправедливостью распределения разность между максимальным количеством конфет, доставшихся одному ребенку и минимальным количеством конфет, доставшихся одному ребенку. посчитайте детям распределить подарки одним из способов Деда Мороза так, чтобы несправедливость распределения была наименьшей. Входные данныеВ первой строке дано одно целое число n (2≤n≤3000) — количество детей. Вторая строка содержит n+1 целых чисел a1,a2,…,an+1 (1≤ai≤1000). Выходные данныеВыведите единственное число — несправедливость наиболее справедливого распределения подарков. Система оценкиПодЗадание 1. Дополнительные ограничения: n=2. Оценивается в 10 поинтов. ПодЗадание 2. Дополнительные ограничения: n=3. Оценивается в 15 поинтов. ПодЗадание 3. Дополнительных ограничений нет. Оценивается в 75 поинтов. Все подзадачи независимы. Баллы за каждый тест начисляются независимо. Примерывходные данныеСкопировать26 3 4выходные данныеСкопировать1входные данныеСкопировать310 13 20 20выходные данныеСкопировать3входные данныеСкопировать423 42 35 52 100выходные данныеСкопировать29