Permutation without Decreasing Triples

Given an integer \( n \), output a permutation of the first \( n \) natural numbers \(1, 2, \dots, n\) such that the permutation does not contain any strictly decreasing subsequence of length exactly 3. In other words, there should be no indices \(i < j a_j > a_k\).

If more than one valid permutation exists, you may output any of them. If no valid permutation exists, output -1.

Note: You need to read from standard input and output the answer to standard output.

inputFormat

The input consists of a single integer \( n \) on a single line, representing the number of elements in the permutation.

Constraints:

• 1 \( \le n \le 10^5 \)

outputFormat

Output a single line containing \( n \) space-separated integers denoting a permutation of \(1, 2, \dots, n\) that does not contain any strictly decreasing subsequence of length 3. If no valid permutation exists, output -1.

1

1