Constructing a Dominant Subarray Sequence with Maximum Distinct Elements

You are given an integer n (with n ≥ 2). Your task is to construct a sequence a₁, a₂, …, a_n consisting of integers from 0 to 10^9 such that every contiguous subarray of length at least 2 has a dominant element. An element is defined to be dominant in a sequence if its frequency is at least half of the length of that sequence, i.e. it appears at least \(\lceil L/2 \rceil\) times in any subarray of length \(L\) (using LaTeX notation for formulas).

Furthermore, among all such sequences the number of distinct elements (i.e. different numbers) should be maximized.

Observation:

• For a subarray of length 2, each element appears once, so any 2 elements work.
• For a subarray of length 3, a dominant element must appear at least 2 times. Hence a 3-element subarray cannot have 3 distinct values.
• One may prove that for n = 2 the maximum number of distinct elements achievable is 2, for n = 3 it is 2, and for any n ≥ 4 the maximum is 3.

A simple solution that attains this optimum is as follows:

• If n = 2: output the sequence [1, 2].
• If n = 3: output the sequence [1, 1, 2]. (Note that any 3-element sequence with 3 distinct numbers will fail since its only subarray of length 3 would have all elements different.)
• If n ≥ 4: output the sequence [2, 1, 1, …, 1, 3] where the first element is 2, the last element is 3, and all elements in between (exactly n-2 of them) are 1. In any contiguous subarray, the element 1 appears sufficiently many times to be dominant.

Explanation: In the case n ≥ 4, note that:

• If the subarray lies completely within the block of 1's then all numbers are 1.
• If the subarray includes one of the boundaries (2 at the start or 3 at the end), it still contains mostly 1's. For instance, consider the subarray [2, 1, 1] or [1, 1, 3] – in both cases the number 1 appears twice, which is \(\lceil3/2\rceil=2\). Similarly, any longer subarray will have a count of 1's that is at least half its length.

You must output any one valid sequence. The numbers 1, 2 and 3 are valid because they lie in the range \([0, 10^9]\).

inputFormat

The input consists of a single integer n (n ≥ 2), denoting the length of the sequence to be constructed.

outputFormat

Output n integers separated by spaces in one line representing the sequence which satisfies the conditions.

sample

2

1 2