J. Prefix Reversal
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given an array $$$A$$$ of length $$$n$$$, where the array uses one-based indexing (i.e., the elements are $$$A[1], A[2], \dots, A[n]$$$).

Define the following function: 


Function F(i, n, A):
    Reverse(A[1..i]) // Reverse the prefix of length i
    ret ← 0
    For j ← 1 to n:
        ret ← ret + (j × A[j]) // weighted sum
    Return ret

That is, the function reverses the prefix of the array from index $$$1$$$ to $$$i$$$ and then computes the weighted sum.

The function operates on a temporary copy of the array $$$A$$$. That is,

  • The reversal of the prefix $$$A[1..i]$$$ is performed only for the purpose of computing $$$F(i, n, A)$$$.
  • The original array $$$A$$$ remains unchanged after the function call.
  • For each value of $$$i$$$, the function is evaluated independently on the original array.

For the given array $$$A$$$, consider all values $$$F(i, n, A)$$$ for $$$1 \le i \le n$$$. Your task is to output an ordering of indices $$$[p_1, p_2, \dots, p_n]$$$ which is a permutation of $$$\{1, 2, \dots, n\}$$$, such that:

  • If $$$F(i, n, A) \le F(j, n, A)$$$, then index $$$i$$$ appears before index $$$j$$$ in the ordering.
  • If multiple valid orderings satisfy the above condition, output the lexicographically smallest one.
Input

The problem 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\cdot10^5)$$$.
  • The second line of each test case contains $$$n$$$ space-separated integers denoting the elements of the array $$$A$$$. ($$$-10^6\le A_i\le10^6$$$)
It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2\cdot10^5$$$.
Output

For each testcase, output the ordering in a single line separated by spaces.

Example
Input
2
5
0 -1 2 3 -4
5
1 0 1 0 -1
Output
4 3 1 2 5 
1 3 2 4 5
Note

For the first array, the values of the function are:

  • $$$F(1, 5, A) = -4$$$
  • $$$F(2, 5, A) = -3$$$
  • $$$F(3, 5, A) = -8\quad;[1\times2+2\times(-1)+3\times0+4\times3+5\times(-4)]$$$
  • $$$F(4, 5, A) = -16$$$
  • $$$F(5, 5, A) = 4$$$

Sorting the indices by non-decreasing values of $$$F(i, 5, A)$$$ gives the ordering: $$$[4 \; 3 \; 1 \; 2 \; 5]$$$

For the second array, there are two valid orderings that satisfy the constraints:

  • $$$[1 \;\; 3 \;\; 2 \;\; 4 \;\; 5]$$$
  • $$$[3 \;\; 1 \;\; 2 \;\; 4 \;\; 5]$$$

Among these, we output $$$[1 \; 3 \; 2 \; 4 \; 5]$$$ as it is the lexicographically smallest valid ordering.

  • All array indices are one-based.
  • Lexicographical comparison follows the standard rule:
    • an ordering $$$P$$$ is lexicographically smaller than an ordering $$$Q$$$ if, at the first position where they differ, $$$P$$$ contains a smaller value than $$$Q$$$.