Chemical experiments
Limits: 2 sec., 256 MiB
This statement was translated automatically from Ukrainian.
As you already know, Zenyk and Marichka are preparing for the ZNO. This time — in chemistry.
Our heroes have several chemical elements, numbered from 1 to \(n\). Now they are experimenting with them!
Of course, there are certain pairs of substances such that their mixture is explosive. It turned out that all such pairs have a difference in indices equal to either 4 or 7. What a coincidence!
Zenyk wants to mix as many elements as possible, but Marichka forbids him to put them in danger, so he cannot mix explosive pairs.
What is the maximum number of chemical elements our young chemists can safely mix?
Input
The single line contains a single integer \(n\) — the number of chemical elements.
Output
In the first line, print a single integer \(k\) — the maximum number of elements that can be mixed.
In the second line, print \(k\) distinct numbers, sorted in ascending order, — the indices of these elements.
If there are several answers with the maximum \(k\), print any of them.
Constraints
\(40\%\) of tests: \(1 \le n \le 20\).
\(40\%\) of tests: \(n \le 10^5\).
\(20\%\) of tests: \(n \le 10^6\).
Samples
| Input (stdin) | Output (stdout) |
|---|---|
| 4 | 4 1 2 3 4 |
| Input (stdin) | Output (stdout) |
|---|---|
| 7 | 4 1 4 6 7 |
Notes
In the second example, the sets [1, 2, 3, 4], [1, 3, 4, 6], [4, 5, 6, 7] and others are also valid. However, for example, the set [1, 2, 3, 5] is not valid, because elements 1 and 5 should not be mixed.
On the other hand, it can be shown that there is no safe set of five elements for \(n = 7\).
Submit a solution
| Element Type | Created | Who | Problem | Compiler | Result | Time (sec.) | Memory (MiB) | # | Actions |
|---|
| Element Type | Created | Who | Problem | Compiler | Result | Time (sec.) | Memory (MiB) | # | Actions |
|---|