小苯的排列构造
时间限制:C/C++/Rust/Pascal 1秒,其他语言2秒
空间限制:C/C++/Rust/Pascal 256 M,其他语言512 M
Special Judge, 64bit IO Format: %lld

题目描述

小苯对 排列 和 质数 很感兴趣。(不懂定义的话,下方有解释)

小苯想要构造一个排列 p ,满足任意相邻两个位置的数字之差的绝对值都是一个质数。
换句话说,小苯想要你输出一个排列 p,满足对于(1 \le i < n) 的所有 i ,都满足 |p_i - p_{i+1}| 的值是一个质数,你能帮帮他吗?
(可以看下方的样例解释)

输入描述:

输入包含一行一个正整数 n(2 \le n \le 2 \times10^5),表示需要构造的排列长度。

输出描述:

输出包含一行 n 个正整数 [p_1, p_2, p_3 ... p_n] 表示你构造的排列,使得小苯的要求成立。如果有多个解,输出任意一个即可。
如果对于某些 n 不存在满足要求的排列,请输出一个整数:-1
示例1

输入

复制
4

输出

复制
2 4 1 3

说明

首先 [2, 4, 1, 3] 是一个长度为 4 的排列,因为这个数组中 [1, 4] 的每个数字都出现且恰好出现了一次。
其次,对于所有的相邻数字差值:
|2 - 4| = 22是质数
|4 - 1| = 33 是质数
|1 - 3| = 22 是质数

备注:

质数(也叫素数):如果一个数 n 是质数,则闭区间 [1, n] 中,应该只有 1 和 n 能整除 n,其余数字均不可以整除 n。例如 25 都是质数,而 4 并不是质数,因为 [1, 4] 区间中,除了 1, 4,还有 2 也整除 4。特别的,请注意 1 并不是质数。

排列:一个长度为 n 的排列是一个长度为 n 的数列,同时满足恰好 [1, n] 中所有数字都在数组里出现且仅出现一次。例如 [1, 2, 3, 5, 4] 就是一个长度为 5 的排列,[2, 3, 5, 1, 4, 6]就是一个长度为 6 的排列,而 [2, 1, 1, 4, 5] 就不是一个长度为 5 的排列,因为其中 1 出现了两次,并且数组中没有出现 3