Consider the following:
Given a set S1 of positive integers, compute the minimum size of a set S2 (possibly equal to S1) so that F(S1) = F(S2).
Input
The first line of input contains the size of S1.
The second line of input contains the elements of S1, separated by spaces.
Output
A single integer: the minimum size of S2.
Constraints
- 1 ≤ the size of S1 < 219
- 1 ≤ every element of S1 < 219
Notes
- If you use C++ I/O streams, please add
cin.sync_with_stdio(false);before reading the input, in order to improve I/O speed. - The elements of a set are distinct, by definition.
Sample
| Input | Output | Explanation |
|---|---|---|
| 4 5 10 15 25 | 3 | S1 = {5, 10, 15, 25} F(S1) = {5, 10, 15, 25, 27, 29, 31} S2 = {5, 10, 25} F(S2) = {5, 10, 15, 25, 27, 29, 31} |