## DMOPC '21 Contest 5 P5 - Permutations & Primes (Hard Version)

View as PDF

Points: 40 (partial)
Time limit: 5.0s
Memory limit: 256M

Author:
Problem type

The primeness of any permutation of is defined as the sum of all prime absolute differences of consecutive elements. Given an integer , find any permutation of with the maximum primeness over all length permutations.

#### Input Specification

The first and only line of input contains a single integer .

#### Output Specification

Output space-separated integers on a single line, representing a permutation of with the maximum primeness over all length permutations.

#### Sample Input 1

3

#### Sample Output 1

2 3 1

#### Explanation for Sample 1

There are absolute differences of consecutive elements, namely and . Out of these, only is prime, so the primeness of this permutation is .

#### Sample Input 2

6

#### Sample Output 2

3 6 1 4 2 5

#### Explanation for Sample 2

The absolute differences of consecutive elements are . All of these are prime, so the primeness of this permutation is .