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. Note: A prime number is a number greater than or equal to 22 that is not divisible by any positive integer except 11 and itself. For example, 2,5,132,5,13 are prime numbers, but 11 and 66 are not prime numbers. A permutation of 1,2,…,n1,2,…,n is an array consisting of nn distinct integers from 11 to nn in arbitrary order. For example, [2,3,1,5,4][2,3,1,5,4] is a permutation, but [1,2,2][1,2,2] is not a permutation (22 appears twice in the array), and [1,3,4][1,3,4] is also not a permutation (n=3n=3 but there is 44 in the array).

To find a permutation of 1, 2, ..., n with the maximum possible primality, we can use the following approach:

1. If n is 1, return [1] as the permutation.
2. If n is 2, return [2, 1] as the permutation. This guarantees that the MEX is 1, which is a prime number.
3. If n is 3, return [3, 1, 2] as the permutation. Again, this guarantees that the MEX is 1, which is a prime number.
4. If n is greater than 3, we can construct the permutation as follows:
- Start with [2, 3, 1], which guarantees that the MEX of the first three elements is 4.
- Append the remaining numbers from 4 to n in any order.

Here's an example implementation in Python:

def max_prime_permutation(n):
    if n == 1:
        return [1]
    elif n == 2:
        return [2, 1]
    elif n == 3:
        return [3, 1, 2]
    else:
        permutation = [2, 3, 1] + list(range(4, n + 1))
        return permutation

n = int(input("Enter a positive integer: "))
permutation = max_prime_permutation(n)
print("Permutation:", permutation)

This approach ensures that the MEX of any consecutive subarray of the permutation is always a prime number.