Permutation Construction

This is one of those problems that looks like nasty inversion-interval soup, but the whole thing collapses after one good re-encoding.

Observation 1: interval sums become prefix differences

Let

$$r_i = \sum_{k=1}^{i-1} a_k \, , \qquad 1 \le i \le n.$$

So $r_1=0$, $r_2=a_1$, $r_3=a_1+a_2$, and so on.

Then for any inversion $(i,j)$ with $i<j$, its value is

$$\sum_{k=i}^{j-1} a_k = r_j-r_i.$$

So the beauty is

$$\sum_{(i,j)\text{ inversion}} (r_j-r_i).$$

That’s already much less cursed.

Observation 2: a permutation is just an order of positions

Instead of constructing the values of the permutation directly, look at the positions in order of decreasing permutation value.

Let

$$q_1,q_2,\dots,q_n$$

be the positions such that

$$p_{q_1} > p_{q_2} > \dots > p_{q_n}.$$

This order completely determines the permutation: the first position gets value $n$, the second gets $n-1$, etc.

So now the problem is:

• choose an order of positions,
• then assign values $n,n-1,\dots,1$ in that order.

Observation 3: compare only two positions

Take any two positions $x$ and $y$.

What happens if $x$ is before $y$ in $q$ versus $y$ before $x$?

Case 1: $x<y$

• If $x$ is before $y$, then $p_x>p_y$, so $(x,y)$ is an inversion and contributes $$r_y-r_x.$$
• If $y$ is before $x$, then $p_x<p_y$, so this pair contributes $0$.

Thus

$$\text{contribution}(x\text{ before }y)-\text{contribution}(y\text{ before }x)=r_y-r_x.$$

Case 2: $x>y$

Now the relevant pair is $(y,x)$.

• If $x$ is before $y$, then $p_x>p_y$, but the indices are reversed, so $(y,x)$ is not an inversion. Contribution $0$.
• If $y$ is before $x$, then $(y,x)$ is an inversion and contributes $$r_x-r_y.$$

So again,

$$\text{contribution}(x\text{ before }y)-\text{contribution}(y\text{ before }x)=r_y-r_x.$$

Same formula. Very nice. Very suspiciously nice.

Observation 4: adjacent swap argument

Suppose in the order $q$ two adjacent positions are $x, y$.

If we swap them, all other pairs stay in the same relative order. So the only change in beauty comes from this pair.

If the current order is $x$ before $y$, then swapping gives change

$$\Delta = \text{beauty}(y,x)-\text{beauty}(x,y)=r_x-r_y.$$

So:

• if $r_x>r_y$, then $\Delta>0$ and swapping improves the answer;
• therefore, in an optimal order, you can never have an adjacent pair with $r_x>r_y$.

That means the optimal order must have

$$r_{q_1} \le r_{q_2} \le \dots \le r_{q_n}.$$

Boom. The whole problem is just sorting positions by $r_i$.

Construction

1. Compute $$r_i = \sum_{k=1}^{i-1} a_k.$$
2. Sort indices $1,2,\dots,n$ by nondecreasing $r_i$.
3. If the sorted order is $ord_1,ord_2,\dots,ord_n$, assign $$p_{ord_1}=n,\quad p_{ord_2}=n-1,\quad \dots,\quad p_{ord_n}=1.$$

If some $r_i$ are equal, any relative order among them is optimal, because swapping equal keys changes nothing.

Why this is correct

The exchange argument is enough:

• any adjacent inversion in the order of keys $r_i$ can be swapped to increase (or preserve) beauty;
• by repeatedly doing this, any optimal order can be transformed into one sorted by nondecreasing $r_i$ without decreasing beauty;
• therefore such a sorted order is optimal.

That’s it. No DP, no segment tree circus, no black magic. Just prefix sums and sorting.

Complexity

For each test case:

• computing prefix sums: $O(n)$,
• sorting indices: $O(n \log n)$,
• constructing the permutation: $O(n)$.

Total complexity over all test cases is

$$O\left(\sum n \log n\right),$$

which is easily fine for $\sum n \le 2\cdot 10^5$.

Memory usage is $O(n)$.