Right Maximum

Research Notes I checked the Codeforces statement/tags (https://codeforces.com/problemset/problem/2204/B), the official Educational Codeforces Round 188 editorial code (https://codeforces.com/blog/entry/152150), CF Step's explanation/code (https://cfstep.com/codeforces/contests/contest-2204/problem-b/), and an independent solution mirror (https://github.com/mhdnazrul/Codeforces-Solutions/blob/main/Solutions/B_Right_Maximum.cpp). They all point to the same intended greedy: count prefix records with ties included. The supplied statement is the source of truth; the explanation below is original.

Core Observation Call an index $i$ a weak prefix maximum if $a_i >= max(a_1,...,a_{i-1})$; for $i=1$, this is automatically true. The answer is exactly the number of weak prefix maxima.

Why weak? Because equal values matter. If the array is $[3,3,3]$, the first operation chooses position $3$, then position $2$, then position $1$. Counting only strict new maxima would output $1$, which is just wrong. Codeforces would bonk that instantly.

Why This Matches The Process Consider the current remaining array as a prefix $a_1,...,a_p$. Let $r$ be the index chosen by the operation: the rightmost position among all maximum values in this prefix.

First, $r$ is a weak prefix maximum. Every element before $r$ is $<= a_r$, because $a_r$ is a maximum of the whole prefix. So it qualifies.

Second, no index $j$ with $r < j <= p$ can be a weak prefix maximum. Since $r$ is the rightmost maximum, every later value satisfies $a_j < a_r$. But $a_r$ is before $j$, so when checking $j$, there is already a previous value larger than it. It fails.

So, in any prefix, the operation chooses exactly the largest-index weak prefix maximum still present. Then it removes that index and everything to its right. In other words, each operation deletes one weak prefix maximum plus some irrelevant smaller junk to its right. Repeating this chooses all weak prefix maxima from right to left.

Therefore, the number of operations is the count of positions $i$ where $a_i >= max(a_1,...,a_{i-1})$.

Algorithm Maintain mx, the maximum value seen so far. Scan left to right:

• If a[i] >= mx, this position is a weak prefix maximum, so increment ans and set mx = a[i].
• If a[i] < mx, it will never be chosen; it gets removed together with some earlier weak prefix maximum.

Because $a_i >= 1$, initializing mx = 0 is safe.

Edge Cases

• Strictly increasing array: every element qualifies, answer $n$.
• Strictly decreasing array: only the first element qualifies, answer $1$.
• All equal values: every element qualifies because ties count, answer $n$.
• Large value followed by smaller values: the smaller suffix adds no operations.

Complexity Each test case is scanned once. Time complexity is $O(n)$, and extra memory is $O(1)$. Across all test cases, the total work is linear in the total input size.