CF2222D.Permutation Construction

Kirara Magic & PIKASONIC - Flora

You are given an array $ a $ consisting of $ n $ integers.

For an inversion $ ^{\text{∗}} $ $ (i,j) $ in a permutation $ ^{\text{†}} $ $ p $ , its value is defined as $ \sum\limits_{k=i}^{j-1} a_k $ . The beauty of a permutation is the sum of the values over all its inversions.

You have to construct a permutation $ p $ of length $ n $ that maximizes its beauty.

$ ^{\text{∗}} $ An inversion in the permutation $ p $ of length $ n $ is a pair of indices $ (i,j) $ such that $ 1\leq i \lt j\leq n $ and $ p_i \gt p_j $ . For example, when $ p=[1,4,2,3,5] $ , the pair $ (2,3) $ is an inversion, but $ (1,2) $ is not an inversion ( $ p_1=1 $ is not greater than $ p_2=4 $ ), and $ (4,2) $ is also not an inversion (the index $ 4 $ is not less than $ 2 $ ). When $ p=[1] $ , there are no inversions at all.

$ ^{\text{†}} $ 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).

Each test contains multiple test cases. The first line contains the number of test cases $ t $ ( $ 1 \le t \le 10^4 $ ). The description of the test cases follows.

The first line of each test case contains a single integer $ n $ ( $ 1\le n \le 2\cdot 10^5 $ ) — the length of $ a $ .

The second line contains $ n $ integers $ a_1, a_2, \ldots, a_n $ ( $ -10^9\leq a_i\leq 10^9 $ ) — the elements of $ a $ .

It is guaranteed that the sum of $ n $ over all test cases does not exceed $ 2\cdot 10^5 $ .

For each test case, print a line containing $ n $ integers — the permutation $ p $ that maximizes its beauty.

If there are multiple valid answers, you may print any of them.

In the first test case, the permutation $ p $ can only be $ [1] $ .

In the second test case, for the permutation $ p=[2,1] $ , the only inversion is $ (1,2) $ , and its value is $ 10^9 $ , so the beauty of the permutation is $ 10^9 $ . It can be proven that there is no permutation with greater beauty.

In the third test case, for the permutation $ p=[3,2,1] $ , all inversions are $ (1,2) $ , $ (1,3) $ , and $ (2,3) $ , with values $ 1 $ , $ 3 $ , and $ 2 $ , respectively, so the beauty of the permutation is $ 1+3+2=6 $ . It can be proven that there is no permutation with a greater beauty.

In the fourth test case, for the permutation $ p=[1,2,3,4] $ , there are no inversions, so the beauty of the permutation is $ 0 $ . It can be proven that there is no permutation with greater beauty.

In the fifth test case, for the permutation $ p=[3,4,1,5,2] $ , its beauty is $ 6 $ .