ENG  RUSTimus Online Judge
Online Judge
Online contests
About Online Judge
Frequently asked questions
Site news
Problem set
Submit solution
Judge status
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests

Ural Championship 2006

About     Problems     Submit solution     Judge status     Standings
Contest is over

G. Christmas gifts

Time limit: 0.5 second
Memory limit: 64 MB
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.


3 7 3 2
1 7
Problem Author: Stanislav Vasilyev
Problem Source: The Xth Urals Collegiate Programing Championship, March 24-25, 2006
To submit the solution for this problem go to the Problem set: 1445. Christmas gifts