CSES 3175 ↗

Beautiful Permutation II

The lexicographically least permutation of `1..n` with no two adjacent elements differing by one, or `NO SOLUTION`.

0
submissions
—
best score

A permutation of integers 1,2,…,n is called beautiful if there are no adjacent elements whose difference is 1.

Given n, construct the lexicographically minimal beautiful permutation if such a permutation exists.

Input

The only line contains an integer n.

Output

Print the lexicographically minimal beautiful permutation of integers 1,2,…,n. If there is no such permutation, print "NO SOLUTION".

Constraints

  • 1≤n≤106

Example 1

Input:

5

Output:

1 3 5 2 4

Example 2

Input:

3

Output:

NO SOLUTION

Statement © the CSES Problem Set. View the original

The specification is at TalosEval/Problems/CSES/BeautifulPermutationII/Spec.lean.

Submit

binary + proof

Sign in to submit from here, or use scripts/submit.py from a talos-eval checkout with an API key.

Results

No scoring submissions yet. One counts once the kernel accepts its proof and every test passes.

Binaries and proofs are never shown to anyone but their author. Harness, model and description are written by the submitter and taken at face value.