Simons and Beating Peaks

Research checked: official Codeforces tutorial, CF Step hints and code, plus maspy's note with an AC submission link. They all point to the same max-Cartesian-tree height formula; the proof below is written from the supplied statement.

Turn operations into survivors

Each operation removes exactly one element. If the final array has $k$ elements, the number of operations is $n-k$, so we want the largest possible set of survivors.

The value $n$ can never be removed. A removed element must be adjacent to a chosen local maximum that is larger than it, and nothing is larger than $n$. Also, in the final cool array, $n$ cannot have survivors on both sides, because then it would be an internal local maximum. So the final survivors are forced into a very narrow shape; this is not a random LIS/LDS problem, despite the temptation.

Cartesian tree view

Build the max Cartesian tree of the permutation:

• inorder traversal gives the original index order,
• every parent has a larger value than its children,
• the root is the position of $n$,
• for two positions $x<y$, their LCA is the position of the maximum value in $a_x,\ldots,a_y$.

Now prove the key claim: the final survivors must form a single ancestor chain in this tree.

Assume two incomparable positions $x<y$ both survive. Let $w=\operatorname{lca}(x,y)$. Then $w$ is the maximum position in the interval $[x,y]$, and $x$ and $y$ lie on opposite sides of $w$.

If $w$ also survives, then in the final array there is some surviving element to the left of $w$ and some surviving element to the right of $w$. Both are smaller than $a_w$, so $w$ becomes an internal peak. That violates coolness.

If $w$ is deleted, it must be deleted while adjacent to a larger value. But every value larger than $a_w$ lies outside $[x,y]$. A larger value on the left can never become adjacent to $w$ because survivor $x$ stays between them; a larger value on the right is blocked by survivor $y$. So $w$ cannot be deleted either. Contradiction.

Therefore no two incomparable nodes can both survive. Since the root $n$ always survives, all survivors lie on one root-to-leaf chain. Hence any valid final array has length at most the height of the max Cartesian tree, where height counts vertices.

Why the bound is achievable

Take a longest root-to-leaf path $P$ in the Cartesian tree. We can keep exactly those nodes.

Process the path from the root downward. At a path node $u$, if it has a child subtree not used by $P$, repeatedly choose $u$ as the local maximum and delete the neighbor on that off-path side. This is legal because $u$ is larger than every value in its child subtrees, and the path continues through the other child whenever an off-path child exists. Once the off-path side is gone, move to the next node of $P$.

After deleting all off-path subtrees, only the path remains. The root and leaf are endpoints. Every other remaining node has its parent adjacent on one side, and the parent is larger, so it cannot be a peak. Thus the path is cool.

So the optimal final length is exactly

$$H[\operatorname{pos}(n)],$$

where $H[u]$ is the height of node $u$ in the max Cartesian tree. The answer is

$$n-H[\operatorname{pos}(n)].$$

Implementation

Build the max Cartesian tree in $O(n)$ using a monotone decreasing stack of indices. For each index $i$:

• pop smaller values; the last popped node becomes the left child of $i$,
• if the stack is still nonempty, $i$ becomes the right child of the stack top,
• push $i$.

Then compute heights without recursion. Since every child has a smaller value than its parent, process values $v=1,2,\ldots,n$. At $u=\operatorname{pos}(v)$,

$$H[u]=1+\max(H[\text{leftChild}[u]], H[\text{rightChild}[u]]).$$

Missing children have height $0$.

Edge cases are automatic: monotone arrays produce a chain of height $n$ and answer $0$; if $n$ is at an endpoint, the root just has one side. Total complexity is $O(n)$ per test case and $O(n)$ memory, so over all tests it is $O(\sum n)$.