Operations with Inversions

The operation removes the right element of an inversion: choose $i<j$ with $a_i>a_j$, then delete $a_j$.

So the whole problem is asking: how many elements can we eventually delete if an element is deletable whenever it has a bigger element somewhere before it?

Key Observation

For an element $a_j$ to be removed, it needs some bigger element to its left at the moment of removal.

Now here is the important part: deleting elements cannot create a new bigger-left element. The order of the remaining elements stays the same, and the only thing operations do is remove stuff. So if $a_j$ did not have a bigger element to its left in the original array, it will never get one later.

That means an element is removable if and only if there already exists an earlier element bigger than it:

$$\exists i<j \text{ such that } a_i>a_j$$

Equivalently, if the maximum value before position $j$ is bigger than $a_j$:

$$\max(a_1, a_2, \ldots, a_{j-1}) > a_j$$

Why every such element can actually be removed

Suppose $a_j$ has a bigger value before it in the original array. Then we can just remove $a_j$ while that bigger value is still present.

Could operations on other elements mess this up? Only if we stupidly delete its witness first. But we are maximizing, not speedrunning bad decisions. We can always remove all currently deletable elements from left to right or right to left while keeping enough earlier bigger elements around. More simply: every counted element has a bigger earlier element, so it is valid to delete it before deleting that earlier element, if needed.

The elements that are not counted are exactly the prefix minima-style survivors: positions whose value is at least every previous value. They cannot be removed because no bigger value exists before them, ever.

So the maximum number of operations is just the count of positions where the previous prefix maximum is greater than the current value.

Algorithm

For each test case:

1. Set mx = 0 because all values are positive.
2. Scan the array from left to right.
3. If mx > a[i], this element can be removed, so increment the answer.
4. Update mx = max(mx, a[i]).

That's it. Rated 800, and for once the trick is not secretly evil.

Correctness Proof

We prove that the algorithm outputs the maximum possible number of operations.

First, consider any element $a_j$ such that no earlier element is greater than it in the original array. Since operations only remove elements and never change the order of the remaining elements, no new earlier greater element can appear later. Therefore $a_j$ can never be removed. So every removable element must satisfy

$$\max(a_1, \ldots, a_{j-1}) > a_j.$$

The algorithm counts exactly those elements.

Now consider any element $a_j$ counted by the algorithm. Then some earlier element $a_i$ satisfies $a_i>a_j$. As long as $a_i$ remains in the array, we may choose the pair $(i,j)$ and remove $a_j$. Thus every counted element is removable under a suitable order of operations.

So no uncounted element can be removed, and every counted element can be removed. Therefore the algorithm's count is exactly the maximum number of operations.

Complexity

Each test case is scanned once.

$$O(n)$$

The memory usage is

$$O(1)$$

besides the input array, and we do not even need to store that.