ENG  RUS Timus Online Judge
Online Judge
Problems
Authors
Online contests
Site news
Webboard
Problem set
Submit solution
Judge status
Guide
Register
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules

## Ural Championship 2006

Contest is over

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

### Input

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.

### Output

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.

### Sample

inputoutput
```4
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