CF1973C Cat, Fox and Double Maximum

Fox loves permutations! She came up with the following problem and asked Cat to solve it: You are given an even positive integer $ n $ and a permutation $ ^\dagger $ $ p $ of length $ n $ . The score of another permutation $ q $ of length $ n $ is the number of local maximums in the array $ a $ of length $ n $ , where $ a_i = p_i + q_i $ for all $ i $ ( $ 1 \le i \le n $ ). In other words, the score of $ q $ is the number of $ i $ such that $ 1 < i < n $ (note the strict inequalities), $ a_{i-1} < a_i $ , and $ a_i > a_{i+1} $ (once again, note the strict inequalities). Find the permutation $ q $ that achieves the maximum score for given $ n $ and $ p $ . If there exist multiple such permutations, you can pick any of them. $ ^\dagger $ A permutation of length $ 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).

The first line of input contains an integer $ t $ ( $ 1 \leq t \leq 10^4 $ ) — the number of test cases in the input you will have to solve. The first line of each test case contains one even integer $ n $ ( $ 4 \leq n \leq 10^5 $ , $ n $ is even) — the length of the permutation $ p $ . The second line of each test case contains the $ n $ integers $ p_1, p_2, \ldots, p_n $ ( $ 1 \leq p_i \leq n $ ). It is guaranteed that $ p $ is a permutation of length $ n $ . It is guaranteed that the sum of $ n $ across all test cases doesn't exceed $ 10^5 $ .

For each test case, output one line containing any permutation of length $ n $ (the array $ q $ ), such that $ q $ maximizes the score under the given constraints.

In the first example, $ a = [3, 6, 4, 7] $ . The array has just one local maximum (on the second position), so the score of the chosen permutation $ q $ is $ 1 $ . It can be proven that this score is optimal under the constraints. In the last example, the resulting array $ a = [6, 6, 12, 7, 14, 7, 14, 6] $ has $ 3 $ local maximums — on the third, fifth and seventh positions.