Math lover Gosha came up with his own sequence. The rules in its sequence are:
1) all numbers in the sequence have their own number;
2) the first element of the sequence has number 1;
3) each number in the sequence must be divisible by its number;
4) the number with a larger number must be no less than the number with a smaller number.
An example of Gosha's sequence:
1 4 6 8 10 18 21.
Given a set of numbers, determine what is the maximum number of numbers that can be chosen to compose the Goshin sequence, as well as what is the maximum number that can be in it.
Input
The first line of the input file contains the number
N - the number of numbers in the file. Next comes
N natural numbers (N <= 10
5), each on a separate line.
Write down in your answer: first, the maximum number of numbers that can be chosen to make the Goshin sequence, then the maximum number that can be in this sequence.
Example input file:
12
25
17
20
15
6
9
10
12
5
3
4
1
Response:
5 25
Assignment file