You are given a positive integer nn. In this problem, the MEXMEX of a collection of integers c1,c2,…,ckc1,c2,…,ck is defined as the smallest positive integer xx which does not occur in the collection cc. The primality of an array a1,…,ana1,…,an is defined as the number of pairs (l,r)(l,r) such that 1≤l≤r≤n1≤l≤r≤n and MEX(al,…,ar)MEX⁡(al,…,ar) is a prime number. Find any permutation of 1,2,…,n1,2,…,n with the maximum possible primality among all permutations of 1,2,…,n1,2,…,n.用中文回答

给定一个正整数n。

在这个问题中，集合c1,c2,…,ckc1,c2,…,ck的MEX（最小排外）定义为不在集合cc中出现的最小正整数xx。

数组a1,…,ana1,…,an的素性定义为对于所有的1≤l≤r≤n1≤l≤r≤n，MEX(al,…,ar)MEX⁡(al,…,ar)是一个质数的对数。

找到所有1,2,…,n1,2,…,n的排列中具有最大可能素性的任意排列。

答案：

一个具有最大可能素性的排列是将所有质数放在前面，然后将所有非质数放在后面。

首先，我们需要找到1到nn之间的所有质数。然后，我们将这些质数按照从小到大的顺序放入一个列表中。

接下来，我们将剩余的非质数（即除了质数之外的所有数字）按照从小到大的顺序放入另一个列表中。

最后，我们将两个列表连接起来，即先放置质数列表，再放置非质数列表。

这样，我们得到了一个具有最大可能素性的排列。