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

В этом году Гарри твердо решил рассчитать все заранее. Он выписал всех своих друзей и отметил, кто с кем знаком. В итоге оказалось, что друзей Гарри можно разделить на несколько компаний так, что человек из одной компании точно не обменивается подарками ни с кем из другой компании. Гарри решил, что просто не будет дарить подарки, полученные от одного человека в компании, другому человеку из этой же компании.

Но есть тут одна загвоздка: конечно, если Гарри сам выбирает очередность обмена подарками, то он сможет оптимизировать процесс, чтобы обойтись минимальным числом подарков. А вот если друзья будут проявлять лишнюю инициативу, то у Гарри в нужный момент может и не оказаться подарка от другой компании друзей. Помогите Гарри посчитать, сколько подарков необходимо приготовить в самом худшем и самом лучшем для него случаях. Можно считать, что за один раз Гарри обменивается подарком только с одним из друзей и все остальные не знают, какой подарок он получил или подарил.

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

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