ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила

1445. Рождественские подарки

Ограничение времени: 0.5 секунды
Ограничение памяти: 64 МБ
Опять приближается Рождество, а значит, Гарри должен готовить всем друзьям и знакомым подарки. Раньше Гарри всегда использовал «принцип первого подарка» — то есть, готовил на Рождество всего один подарок. Когда надо было кого-то поздравлять, торжественно вручал имеющийся подарок, а взамен, разумеется, получал другой подарок, который и дарил следующему другу. Но в прошлое рождество он получил в подарок от Фреда тот самый (оставшийся с прошлого Рождества) сломанный кристалл, который сам Гарри подарил Рону. А Джордж, оказывается, подарил Рону дракончика, и получил от него такое же шоколадное яйцо, которое сам Джордж дарил Фреду. Тут Гарри смекнул, что подарил Джорджу как раз того дракончика, которого получил от Рона… а значит, наверняка, та книга, которую Гарри получил от Джорджа и подарил Фреду, тоже вернулась к прежнему хозяину.
В этом году Гарри твердо решил рассчитать все заранее. Он выписал всех своих друзей и отметил, кто с кем знаком. В итоге оказалось, что друзей Гарри можно разделить на несколько компаний так, что человек из одной компании точно не обменивается подарками ни с кем из другой компании. Гарри решил, что просто не будет дарить подарки, полученные от одного человека в компании, другому человеку из этой же компании.
Но есть тут одна загвоздка: конечно, если Гарри сам выбирает очередность обмена подарками, то он сможет оптимизировать процесс, чтобы обойтись минимальным числом подарков. А вот если друзья будут проявлять лишнюю инициативу, то у Гарри в нужный момент может и не оказаться подарка от другой компании друзей. Помогите Гарри посчитать, сколько подарков необходимо приготовить в самом худшем и самом лучшем для него случаях. Можно считать, что за один раз Гарри обменивается подарком только с одним из друзей и все остальные не знают, какой подарок он получил или подарил.

Исходные данные

В первой строке находится число N (1 ≤ N ≤ 500) — количество разных компаний друзей Гарри. В следующей строке находятся N чисел от 1 до 500, каждое обозначает количество друзей в соответствующей компании.

Результат

Вывести через пробел два числа — «лучшее минимальное» (когда Гарри сам выбирает последовательность встреч с друзьями) и «худшее минимальное» (когда Гарри совсем не контролирует последовательность обменов) количество подарков, необходимое для того, чтобы каждый человек получил от Гарри подарок, либо приготовленный самим Гарри, либо подаренный кем-то из другой компании.

Пример

исходные данныерезультат
4
3 7 3 2
1 7
Автор задачи: Станислав Васильев
Источник задачи: X командный Чемпионат Урала по спортивному программированию, 24-25 марта 2006 года