Problem Description

Construct a sequence of length $n$ such that every subarray of length at least $2$ has a majority element. Based on this, maximize the number of distinct values in the sequence. The majority element of a sequence is defined as a number whose occurrence count is at least half of the sequence length.

Each element in your constructed sequence must be an integer between $0$ and $10^9$.

Input Format

One line containing a positive integer $n$.

Output Format

One line containing $n$ integers, representing the sequence you constructed. If there are multiple answers, output any one of them.

3

1 1 2

Hint

This problem uses bundled tests.

Constraints:

• Subtask 1 (10pts): $n \le 5$.
• Subtask 2 (40pts): $n$ is a multiple of $3$.
• Subtask 3 (50pts): No special restrictions.

For all data, $1 \le n \le 10^3$.

Translated by ChatGPT 5