题目描述

难度分:$1000$

输入$T(\leq 10^4)$表示$T$组数据。所有数据的$n$之和$\leq 2 \times 10^5$。每组数据输入$n(2 \leq n \leq 2 \times 10^5)$。

构造一个$1$~$n$的排列，满足任意相邻两数之和都是合数。如果无法构造，输出$-1$。

输入样例

2
3
8

输出样例

-1
1 8 7 3 6 2 4 5

算法

奇偶分组

首先可以发现一点的是奇偶性相同的两个数是肯定可以相邻的，因为奇偶性相同的两个数就是偶数，偶数肯定存在因子$2$，所以肯定能挨在一起。那此时我们就只需要考虑奇偶之间的分界线，把分界线两侧的一奇一偶凑出一个合数来。

而奇数$+$偶数$=$奇数，找到第一个属于合数$9$。让和为$9$的两个数中较大的那个尽可能小，$4+5=9$，这时候就可以知道$n \geq 5$时都是有解的，把奇数排在前面，把偶数排在后面（反过来也行），分界线的位置是$5$和$4$。至于$n \lt 5$的情况，枚举一下全排列可以发现无解，直接输出$-1$。

复杂度分析

时间复杂度

由于是直接构造出来长度为$n$的排列，所以时间复杂度为$O(n)$。

空间复杂度

整个过程只使用了有限几个变量，额外空间复杂度为$O(1)$。

$python$代码

t = int(input())
for _ in range(t):
    n = int(input())
    if n >= 5:
        for i in range(1, n + 1, 2):
            if i == 5:
                continue
            print(i, end=' ')
        print(5, end=' ')
        print(4, end=' ')
        for i in range(2, n + 1, 2):
            if i == 4:
                continue
            print(i, end=' ')
    else:
        print(-1)