Little Gyro has just found an integer sequence in his left pocket. As Little Gyro is bored, he decides to delete some elements from the sequence.
However, Little Gyro's father, Mr.Potato, is aware of Little Gyro's attitude, so he gives Little Gyro a task to do. The problem is how to delete some strictly increasing subsequences from his left pocket within the least operations as well as containing the most elements until his left pocket is empty.
Now given an integer sequence, and within his father's command, Little Gyro is ready to delete the sequence. Could you help him to find the number of subsequences at least and the number of the elements for the longest subsequence at most?
For example, let's consider the sequence [1,2,3]. All the subsequences of [1,2,3] are [1], [2], [3], [1,2], [1,3], [2,3], [1,2,3].
And the sequence [1,2,3] is a strictly increasing subsequence. However, [1,1,2], [3,1,2] are not.

Each input file only contains one test case.
The first line contains an integer n (1 ≤ n ≤ 2×), indicating the length of the sequence.
The second line contains n integers  (1 ≤  ≤ ), indicating the given sequence.

For each test case output two integers, indicating the number of the elements for the longest subsequence and the number of subsequences Little Gyro will delete at least.

5
1 2 2 3 1

3 3

5
1 1 1 1 1

1 5

For the first sample, Little Gyro can delete 3 subsequences [1,2,3], [2], [1] at least, the length of  the longest subsequence is 3, so the answer is 3 3.
For the second sample, Little Gyro only can delete subsequence [1] for 5 times.