It Just Keeps Going Sideways

Observation 1: rows are independent

At height $h$, define a binary row:

$$b_i(h) = [a_i \ge h].$$

So the row contains cubes exactly in columns where $a_i \ge h$.

After gravity points right, those cubes slide to the rightmost possible columns, preserving order inside the row. If the occupied columns are

$$p_1 < p_2 < \dots < p_k,$$

then after shifting they end up at

$$n-k+1,\ n-k+2,\ \dots,\ n.$$

So the contribution of this row is

$$D_h = \sum_{r=1}^{k} \bigl((n-k+r)-p_r\bigr).$$

That part is standard. The real trick is what happens when we remove one cube.

Observation 2: one deletion changes exactly one row

If we decrease $a_i$ by $1$, we remove the top cube of column $i$, i.e. the cube at height $h=a_i$.

That means:

• rows $< h$ are unchanged,
• row $h$ loses exactly one occupied cell,
• rows $> h$ were already empty in column $i$.

So the whole operation affects only one row. That’s the key. If you missed it, the problem looks way nastier than it actually is.

Observation 3: the gain from deleting column $i$ has a tiny formula

Fix a row with occupied positions

$$p_1 < p_2 < \dots < p_k.$$

Suppose we remove the cube at $p_t=i$.

Originally, that cube ends at position

$$q_t = n-k+t.$$

So its own contribution was

$$q_t - i = n-k+t-i.$$

What about the other cubes?

• Cubes before it ($r<t$) keep the same rank, but now there is one fewer cube total, so the packed block shifts one step right. Each of them gains $+1$ movement.
• Cubes after it ($r>t$) effectively move into the removed cube’s old target slot, so their final positions stay the same.

Therefore the total change is

$$\Delta = (t-1) - (n-k+t-i).$$

The $t$ cancels out like magic:

$$\Delta = i + k - n - 1.$$

Now for column $i$, the relevant row is $h=a_i$, and in that row

$$k = c_{a_i},$$

where $c_h$ is the number of columns with height at least $h$.

So the gain from deleting the top cube of column $i$ is simply

$$\Delta_i = i + c_{a_i} - n - 1.$$

That’s hilariously small given how evil the statement looks.

So if $S$ is the initial total movement, the final answer is

$$S + \max\left(0, \max_{1\le i\le n} \Delta_i\right).$$

We can compute all $c_h$ using a frequency array and suffix sums.

Observation 4: compute the initial total with pair contributions

Now we need $S$ for the original array.

Here’s the cleanest viewpoint: look at a pair of columns $(i,j)$ with $i<j$. A cube from column $i$ contributes $1$ movement across column $j$ at exactly those heights where:

• column $i$ has a cube, and
• column $j$ does not.

That means heights

$$a_j < h \le a_i.$$

The number of such heights is

$$\max(0, a_i-a_j).$$

Therefore,

$$S = \sum_{1\le i<j\le n} \max(0, a_i-a_j).$$

So we reduced the geometry mess to a plain array sum. Much nicer.

Data structure for $S$

Scan from left to right. When processing $a_j=x$, we need

$$\sum_{i<j} \max(0,a_i-x) = \sum_{i<j,\ a_i>x} (a_i-x).$$

If among previous elements greater than $x$ we know:

• their count = $cnt_{>x}$,
• their sum = $sum_{>x}$,

then the added contribution is

$$sum_{>x} - x\cdot cnt_{>x}.$$

So maintain two Fenwick trees over height values $1..n$:

• one for counts,
• one for sums of heights.

Each step costs $O(\log n)$.

Correctness sketch

Lemma 1

At a fixed height $h$, after rightward gravity, the occupied cells become the rightmost $k$ columns, where $k=c_h$.

This is immediate: cubes move right as far as possible, cannot overlap, and keep their height.

Lemma 2

If we delete the top cube of column $i$, only row $h=a_i$ changes.

Below height $a_i$, the column still contains cubes. At height $a_i$, the cube disappears. Above that height, the column was already empty. Done.

Lemma 3

Deleting the cube at column $i$ changes the total movement by

$$\Delta_i = i + c_{a_i} - n - 1.$$

Proof: in row $h=a_i$, if the removed cube is the $t$-th occupied cube among $k=c_{a_i}$ occupied cubes, then:

• $t-1$ cubes before it gain $1$ each,
• cubes after it are unchanged,
• the removed cube loses its old contribution $n-k+t-i$.

Hence

$$\Delta_i=(t-1)-(n-k+t-i)=i+k-n-1.$$

Lemma 4

The initial total movement equals

$$S = \sum_{i<j} \max(0,a_i-a_j).$$

For each pair $(i,j)$, column $i$ contributes one unit of movement across column $j$ for every height where $i$ has a cube and $j$ does not, i.e. for exactly $\max(0,a_i-a_j)$ heights. Summing over all pairs gives $S$.

Combining Lemmas 3 and 4 gives the full formula.

Complexity

For each test case:

• computing suffix counts $c_h$: $O(n)$,
• scanning with Fenwick trees for $S$: $O(n\log n)$,
• checking all $\Delta_i$: $O(n)$.

So total complexity is

$$O(n\log n)$$

per test case, and across all test cases still

$$O\bigl((\sum n)\log n\bigr),$$

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

Implementation notes

• Use long long. The answer can get pretty damn large.
• Heights satisfy $1\le a_i\le n$, so Fenwick size $n$ is enough.
• Don’t forget that doing nothing is allowed, so take

$$\max(0, \max_i \Delta_i).$$