The Trip (2007)

A number of students are members of a club that travels annually to exotic locations. Their destinations in the past have included Indianapolis, Phoenix, Nashville, Philadelphia, San Jose, Atlanta, Eindhoven, Orlando, Vancouver, Honolulu, Beverly Hills, Prague, Shanghai, and San Antonio. This spring they are hoping to make a similar trip but aren't quite sure where or when.

An issue with the trip is that their very generous sponsors always give them various knapsacks and other carrying bags that they must pack for their trip home. As the airline allows only so many pieces of luggage, they decide to pool their gifts and to pack one bag within another so as to minimize the total number of pieces they must carry.

The bags are all exactly the same shape and differ only in their linear dimension, which is a positive integer not exceeding $1000000$. A bag with a smaller dimension fits inside one with a larger dimension, but two bags of equal dimension cannot be nested. Determine the minimum number of pieces (outermost bags) needed to pack all of the bags. Among all packings that use this minimum number of pieces, also determine the smallest possible number of bags in the largest piece, where the number of bags in a piece counts every bag nested inside it, including the outermost one.

The input contains several test cases. Each test case begins with an integer $1 \le n \le 10000$, the number of bags, followed by $n$ integers given on one or more lines, each the dimension of one bag. A line containing a single $0$ follows the last test case and must not be processed.

For each test case, print two integers on a single line separated by one space: $k$, the minimum number of pieces, and $m$, the smallest possible number of bags in the largest piece over all packings that use exactly $k$ pieces. Print the answers in the order the test cases appear, one line per test case.