Christmas is approaching, which means that Harry must prepare gifts for all of his friends. Formerly, Harry always used the "first gift principle", that is, he prepared only one Christmas gift and gave it away when he needed to congratulate somebody. Of
course, he received a gift in return and gave it to the next friend, and so on. But last Christmas he got from Fred the same broken crystal (left from the previous Christmas) which Harry himself had given to Ron. And it turned out that George presented Ron with a silver dragon and got from him the same chocolate egg that George had given to Fred.
Then Harry remembered that the silver dragon he had given George had been received from Ron, which meant that the book that Harry had got from George and given to Fred had returned to its owner as well.
This year, Harry decided to calculate everything in advance. He
wrote out the list of his friends and marked there who is
acquainted with whom. It turned out that Harry's friends could be
divided into groups such that a person from one group wouldn't
for sure exchange gifts with anybody from another group. Harry
decided that he simply would not present gifts received from
a friend to any person in the same group.
But there's one problem. Of course, if Harry can choose the order
in which he meets his friends, he can optimize the process to get by
with the minimal number of gifts. But if his friends come when they
want, then at some moments Harry may have no gift from another group
of friends to present his guest with.
Help Harry to calculate how many gifts he must prepare in the best
and in the worst cases. You may assume that Harry exchanges gifts
with only one friend at a time and other friends don't know which
gifts are presented.
The first line contains the number of groups of Harry's friends N
(1 ≤ N ≤ 500). The second line contains N numbers
in the range from 1 to 500, each of them being the number of
people in the corresponding group.
You should output two numbers separated with a space. They are the
"best minimal" (when Harry himself chooses the order of his meetings
with friends) and the "worst minimal" (when Harry has no control
over this order at all) numbers of gifts that he must prepare in order
to satisfy the following requirement: each of Harry's friends must receive
from Harry a gift that either was prepared by Harry himself or was presented
to Harry by a person from another group.
Problem Author: Stanislav Vasilyev
Problem Source: The Xth Urals Collegiate Programing Championship, March 24-25, 2006