Arrange Tree Heights

Given a single integer \( n \), arrange a permutation of the first \( n \) natural numbers representing the heights of trees such that no two adjacent trees have identical heights. Although any permutation of unique numbers satisfies this condition, the challenge is to implement a specific algorithm.

The algorithm is defined as follows:

• If \( n = 2 \), output the permutation \( [1, 2] \).
• If \( n > 2 \), fill the positions at even indices (0-indexed) with the smallest numbers in increasing order, then fill the odd indices with the remaining numbers in increasing order.

For example, when \( n = 4 \), a valid output is: 1 3 2 4.

inputFormat

The input is provided on a single line containing an integer ( n ) (( 2 \leq n \leq 10^6 )) representing the number of trees.

outputFormat

Output a single line containing ( n ) space-separated integers which is a permutation of ( {1, 2, \dots, n} ) arranged according to the algorithm.## sample

4

1 3 2 4