CF1844B Permutations & Primes

You are given a positive integer $ n $ . In this problem, the $ \operatorname{MEX} $ of a collection of integers $ c_1,c_2,\dots,c_k $ is defined as the smallest positive integer $ x $ which does not occur in the collection $ c $ . The primality of an array $ a_1,\dots,a_n $ is defined as the number of pairs $ (l,r) $ such that $ 1 \le l \le r \le n $ and $ \operatorname{MEX}(a_l,\dots,a_r) $ is a prime number. Find any permutation of $ 1,2,\dots,n $ with the maximum possible primality among all permutations of $ 1,2,\dots,n $ . Note: - A prime number is a number greater than or equal to $ 2 $ that is not divisible by any positive integer except $ 1 $ and itself. For example, $ 2,5,13 $ are prime numbers, but $ 1 $ and $ 6 $ are not prime numbers. - A permutation of $ 1,2,\dots,n $ is an array consisting of $ n $ distinct integers from $ 1 $ to $ n $ in arbitrary order. For example, $ [2,3,1,5,4] $ is a permutation, but $ [1,2,2] $ is not a permutation ( $ 2 $ appears twice in the array), and $ [1,3,4] $ is also not a permutation ( $ n=3 $ but there is $ 4 $ in the array).

N/A

N/A

In the first test case, there are $ 3 $ pairs $ (l,r) $ with $ 1 \le l \le r \le 2 $ , out of which $ 2 $ have a prime $ \operatorname{MEX}(a_l,\dots,a_r) $ : - $ (l,r) = (1,1) $ : $ \operatorname{MEX}(2) = 1 $ , which is not prime. - $ (l,r) = (1,2) $ : $ \operatorname{MEX}(2,1) = 3 $ , which is prime. - $ (l,r) = (2,2) $ : $ \operatorname{MEX}(1) = 2 $ , which is prime. Therefore, the primality is $ 2 $ .In the second test case, $ \operatorname{MEX}(1) = 2 $ is prime, so the primality is $ 1 $ . In the third test case, the maximum possible primality is $ 8 $ .