Let the original array be:

After gravity shifts to the right, the final configuration is equivalent to sorting the heights in non-decreasing order. Let the sorted array be:

Instead of tracking every cube individually, we can compute the answer using weighted positional sums.

Define:

and

Then the total movement of all cubes is simply:

Therefore, once the array is fixed, the answer can be computed in O(n log n) by sorting the heights and evaluating the two sums.

We are allowed to decrease exactly one height by 1.

Suppose we decrease the height of column i. Instead of recomputing the entire answer for every position, we only need to know how much extra movement this removal creates.

Claim: The increase in total movement is exactly equal to the number of elements on its left having value greater than or equal to a_i.

Define:

Then the optimal move is to choose the index having maximum value of greater_i.

A naive approach checks every previous element for every position.

Complexity:

which is too slow.

We instead use:

• Coordinate Compression

• Fenwick Tree (Binary Indexed Tree)

For every position:

1. Compress the value to its rank.

2. Query how many strictly smaller values have already appeared.

Let this value be

Since there are i−1 previous elements,

Fenwick Tree supports update and query operations in

Therefore all greater_i values are computed in

Coordinate Compression:

Fenwick Tree Processing:

Sorting:

Overall Complexity:

Memory Complexity:

This approach views the problem through positional sums and uses a Fenwick Tree to determine the optimal column to decrease.

I found this observation quite intuitive because the entire effect of the operation can be reduced to counting how many previous heights are greater than or equal to the current height.

Any suggestions, alternative proofs, or improvements are welcome.