It All Went Sideways

Observation 1: think in rows, not in columns

If you stare at the columns too hard, the problem starts looking cursed. Don’t do that.

Fix a height $h$. Look only at cubes on that row. Suppose they occupy columns $p_1 < p_2 < \dots < p_k.$ After gravity points right, these $k$ cubes slide as far right as possible, preserving order, so they end up at $n-k+1,\ n-k+2,\ \dots,\ n.$

So when does a cube on this row not move? Exactly when its original position already equals its final one. That means the stationary cubes on a row are precisely the cubes in the rightmost consecutive occupied suffix of that row.

Example: if a row looks like $[1,0,1,1,1],$ then after shifting right it becomes $[0,1,1,1,1].$ Only the last $3$ cubes were already forming the right suffix, so only those $3$ stay.

---

Observation 2: stationary cubes form suffix minima

Now translate that row condition back into columns.

Take a cube at column $i$ and height $h$. It stays in the same column iff in row $h$, columns $i,i+1,\dots,n$ are all occupied. In other words, $a_i \ge h,\ a_{i+1} \ge h,\ \dots,\ a_n \ge h.$ That is equivalent to $h \le \min_{k=i}^n a_k.$

So column $i$ contributes exactly $m_i = \min(a_i,a_{i+1},\dots,a_n)$ stationary cubes.

Therefore the total number of stationary cubes is $\sum_{i=1}^n m_i,$ where $m_i$ is the suffix minimum.

Since the total number of cubes is $S = \sum_{i=1}^n a_i,$ the number of moved cubes without using the operation is $S - \sum_{i=1}^n m_i.$

That’s already half the problem done. The other half is: what happens if we decrease one $a_j$ by $1$?

---

Observation 3: decreasing one column only affects some suffix minima

Suppose we decrease $a_j$ to $a_j-1$.

For any $i > j$, the suffix $[i,n]$ does not include position $j$, so $m_i$ stays unchanged.

For any $i \le j$, the new suffix minimum is $m_i' = \min(m_i, a_j-1).$ Because $j \in [i,n]$, we always have $m_i \le a_j.$ So the only way $m_i$ changes is when $m_i = a_j,$ in which case it drops by exactly $1$.

That’s the key insight. No DP wizardry, no black magic. Just suffix minima being brutally simple.

So if we decrease position $j$, the total stationary count decreases by $c_j = \#\{i \le j : m_i = a_j\}.$ At the same time, total cubes decrease by exactly $1$.

Hence the moved count changes by $(-1) - (-c_j) = c_j - 1.$

So the final answer is

$$\left(\sum_{i=1}^n a_i - \sum_{i=1}^n m_i\right) + \max\left(0, \max_{1 \le j \le n}(c_j - 1)\right).$$

---

Observation 4: how to compute $c_j$ fast

We need $c_j = \#\{i \le j : m_i = a_j\}.$

Now notice that $m_i$ is the suffix minimum array, so it is nondecreasing from left to right: $m_1 \le m_2 \le \dots \le m_n.$

If $a_j \ne m_j$, then actually $c_j = 0$. Why? Because if $a_j > m_j$, then there is a smaller value somewhere to the right of $j$, so decreasing $a_j$ does nothing to any suffix minimum.

If $a_j = m_j$, then $c_j$ is just the number of times value $a_j$ has appeared in the prefix $m_1, m_2, \dots, m_j$.

So we can scan from left to right, maintain a frequency table of seen suffix minima, and for each position $j$:

• add $m_j$ to the table,
• if $a_j = m_j$, candidate gain is $\text{freq}[a_j] - 1.$

Take the maximum candidate gain, or $0$ if doing nothing is better.

---

Algorithm

For each test case:

1. Read $a$ and compute $S = \sum a_i.$
2. Compute suffix minima: $m_n = a_n, \qquad m_i = \min(a_i, m_{i+1}).$
3. Compute $U = \sum m_i.$ Then base moved count is $S-U.$
4. Scan left to right, maintaining freq[value] = how many times this suffix minimum value has appeared so far.
5. For each $j$:
   • increment freq[m_j],
   • if $a_j = m_j$, update $\text{bestGain} = \max(\text{bestGain},\ \text{freq}[a_j]-1).$
6. Answer is $S-U+\text{bestGain}.$

---

Why this is correct

We already proved:

• stationary cubes in column $i$ are exactly the first $m_i = \min_{k=i}^n a_k$ heights,
• decreasing $a_j$ only changes suffix minima for $i \le j$,
• such a suffix minimum drops iff it was exactly $a_j$,
• each affected suffix minimum drops by exactly $1$.

Therefore decreasing $a_j$ decreases the stationary total by exactly $c_j = \#\{i \le j : m_i = a_j\},$ while decreasing the total cube count by $1$. So the number of moved cubes increases by $c_j-1$. Maximizing over all $j$ (and comparing with doing nothing) gives the formula above.

No gaps, no handwaving, no "trust me bro".

---

Complexity

Each test case is processed in linear time:

• computing suffix minima: $O(n)$,
• summing values: $O(n)$,
• frequency scan: $O(n)$.

So total complexity is $O(n)$ per test case, and overall $O\left(\sum n\right),$ which fits comfortably under the constraints.

Memory usage is also linear: $O(n).$

Pretty damn efficient for something that initially looks like it wants a physics engine.