Nils, Canada's most popular interior designer, has been tasked with selecting aesthetically pleasing potted plants!
There are species of plants, labelled between and , where plants of the same species look identical. Nils has been asked to form a straight line of pots, where each pot contains one of the types of plants, subject to the following constraints:
- The display of plants is symmetrical, that is, the sequence of plants is palindromic.
- For visual appeal, no two different contiguous sections of pots should contain identical sequences of plants, with both sequences containing more than one plant. Formally, every contiguous subsequence of the plants with a length greater than should be unique.
Nils will be paid more for selecting a greater number of plants, so he wishes to maximise the value of .
Can you help him find an optimal selection of plants?
Subtask 1 [40%]
Subtask 2 [60%]
No additional constraints.
The only line contains a single integer, .
Output space-separated integers, corresponding to the sequence of selected plants. Any valid sequence which maximises will be accepted.
1 2 2 1
This sequence has , is palindromic, and satisfies the condition that every contiguous subsequence with a length greater than is unique. It can be shown that this is the largest possible value of .