DMOPC '21 Contest 5 P2 - Permutations & Primes

View as PDF

Submit solution


Points: 7
Time limit: 2.0s
Memory limit: 256M

Author:
Problem type

Given an integer N, find any permutation p_1, p_2, \dots, p_N of 1, 2, \dots, N such that p_1 + p_2 + \dots + p_{i-1} + p_i is not prime for every integer 1 \le i \le N, or report that no such permutation exists.

Constraints

1 \le N \le 10^6

Input Specification

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

Output Specification

If there exists no valid permutation, output -1 on a line by itself.

Otherwise, output N space-separated integers on a single line, representing a permutation p_1, p_2, \dots, p_N of 1, 2, \dots, N where no prefix sum is prime.

Sample Input

5

Sample Output

4 5 3 2 1

Explanation

The prefix sums are: p_1 = 4, p_1 + p_2 = 9, p_1 + p_2 + p_3 = 12, p_1 + p_2 + p_3 + p_4 = 14, and p_1 + p_2 + p_3 + p_4 + p_5 = 15.

None of 4, 9, 12, 14, or 15 are prime, so this is a valid permutation.


Comments

There are no comments at the moment.