Hints: Right Maximum

After each operation, you remove the rightmost maximum and everything to its right. So the remaining array is always a prefix of the original array.

If after some operations the remaining array is $a[1 \ldots p]$ (1-indexed), who is chosen in the next operation?

Answer to Hint 1: The next chosen element is the rightmost maximum in $a[1 \ldots p]$. So you need, for every prefix length $p$, the index (or position) of the rightmost maximum in that prefix.

How can you compute that for all $p$ in one pass?

Answer to Hint 2: Scan left to right and maintain a prefix maximum: for each $i$, store the (value, index) of the maximum in $a[0 \ldots i]$. When there are ties, “max” naturally keeps the rightmost if you use a comparison that prefers the later index when values are equal (e.g. std::max(pre[i], make_pair(a[i], i)) so that when values are equal, the larger index wins).

So pre[p] = (max value in prefix of length p, index of that maximum). The index is exactly the rightmost position of the max in $a[0..p-1]$.

Answer to Hint 3: Simulate the operations without actually modifying the array. Start with $p = n$ (the full array). In each step: the rightmost max in the current prefix $[0, p)$ is at index pre[p].second. So we remove from that index onward — meaning the new “prefix” has length pre[p].second. Set $p \leftarrow \texttt{pre[p].second}$ and increment the operation count. Stop when $p = 0$.

Answer to Hint 4: Implementation: build pre[0] = (-1, -1) or similar, then for $i = 0..n-1$, pre[i+1] = max(pre[i], (a[i], i)) (so index is 0-based). Then ans = 0, p = n; while p > 0: ans++, p = pre[p].second. Output ans.