Hints: Permutation Construction

Hint 1 ↕

For an inversion $(i, j)$, the value is a subarray sum:

$$ a_i + a_{i+1} + \cdots + a_{j-1}. $$

Try to rewrite this using prefix sums. Which two prefix sums does it compare?

Hint 2 ↕

Answer to Hint 1: Define $b_i$ as the sum of elements before position $i$:

$$ b_i = a_1 + a_2 + \cdots + a_{i-1}. $$

Then for $i < j$,

$$ \sum_{k=i}^{j-1} a_k = b_j - b_i. $$

So the value of choosing an inversion between positions $i$ and $j$ depends only on the two numbers $b_i$ and $b_j$.

Hint 3 ↕

Now look at a fixed pair of positions $i < j$. There are only two possibilities:

If $p_i > p_j$, the pair is an inversion and contributes $b_j - b_i$.
If $p_i < p_j$, the pair is not an inversion and contributes $0$.

For this one pair alone, when would you want it to be an inversion?

Hint 4 ↕

Answer to Hint 3: If $b_j - b_i$ is positive, making $(i, j)$ an inversion is good. If $b_j - b_i$ is negative, making it an inversion is bad. If it is zero, it does not matter.

So ideally, for every pair $i < j$, we want:

$p_i > p_j$ when $b_i < b_j$,
$p_i < p_j$ when $b_i > b_j$.

Can all these pairwise wishes be satisfied at the same time?

Hint 5 ↕

Answer to Hint 4: Yes. The desired relation only depends on comparing the prefix values $b_i$.

Positions with smaller $b_i$ should receive larger permutation values. Positions with larger $b_i$ should receive smaller permutation values.

So the whole problem is starting to look like: sort the positions by $b_i$.

Hint 6 ↕

Why does sorting by $b_i$ satisfy all pairs at once?

Suppose $b_i < b_j$. If position $i$ gets a larger permutation value than position $j$, then whenever $i < j$, the pair $(i, j)$ becomes an inversion and contributes the positive amount $b_j - b_i$.

If $b_i > b_j$, position $i$ gets a smaller value than position $j$, so $(i, j)$ is not an inversion and the negative amount is avoided.

Hint 7 ↕

This also gives a clean correctness proof.

For every pair $i < j$, the best contribution that pair could possibly give is $\max(0, b_j - b_i)$, because the pair either contributes $b_j - b_i$ or contributes $0$.

Therefore, the total beauty of any permutation is at most the sum of these pairwise best values.

Hint 8 ↕

Answer to Hint 7: The sorted construction reaches exactly that upper bound.

If $b_j > b_i$, the position with smaller prefix value gets the larger permutation value, so $(i, j)$ is an inversion and contributes $b_j - b_i$.

If $b_j < b_i$, it is not an inversion, so it contributes $0$.

If $b_j = b_i$, either choice contributes $0$. Thus every pair contributes its own maximum possible value.

Hint 9 ↕

Now translate the idea into construction.

Compute the $n$ values

$$ b_1 = 0,\quad b_2 = a_1,\quad b_3 = a_1 + a_2,\quad \ldots,\quad b_n = a_1 + \cdots + a_{n-1}. $$

Notice that $a_n$ is not needed for these prefixes, because no inversion value ends after position $n$ and includes $a_n$.

Hint 10 ↕

Sort the positions by increasing $b_i$.

Then assign permutation values from large to small in that order:

the smallest $b_i$ gets $n$,
the next smallest gets $n-1$,
and so on,
the largest $b_i$ gets $1$.

Ties can be broken arbitrarily, since equal prefix values only create zero-value choices between those positions.

Hint 11 ↕

Implementation details:

Use 64-bit integers for prefix sums, because $a_i$ can be up to $10^9$ and $n$ can be large.

Create an array of indices $0, 1, \ldots, n-1$, where index $i$ represents position $i+1$ and has prefix value pref[i]. Sort these indices by pref[i]. If an index is the $r$-th in this sorted order, assign it value $n-r$.

The complexity is $O(n \log n)$ per test case because of sorting, which is enough for the given constraints.