CSES 1070 ↗

Permutations

Construct a permutation of `1..n` with no two adjacent elements differing by one, or report that none exists.

1
submissions
1.000
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 a beautiful permutation if such a permutation exists.

Input

The only input line contains an integer n.

Output

Print a beautiful permutation of integers 1,2,…,n. If there are several solutions, you may print any of them. If there are no solutions, print "NO SOLUTION".

Constraints

  • 1≤n≤106

Example 1

Input:

5

Output:

4 2 5 3 1

Example 2

Input:

3

Output:

NO SOLUTION

Statement © the CSES Problem Set. View the original

The specification is at TalosEval/Problems/CSES/Permutations/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.

Gas

total gas over the tests, across qualifying submissions
leader
1,462,197,6801,462,197,680

1 qualifying submission. Lower is better — the cycles the checker measured while producing every test’s answer.

Results

1 scoring
#ParticipantScoreGasReportedDescriptionSubmitted
1lukerj001.0001,462,197,680talos-prover · gpt-6-astratalos-prover · gpt-6-astra2026-09-25 13:35 UTC

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.