Hints: Simons and Beating Peaks
The three model solutions (model_sol.cpp, model_sol_2.cpp, model_sol_3.cpp) all compute the same quantity. Each section below is a separate route to that answer: Cartesian tree + value DP, two monotone stacks, or divide & conquer with a range-max structure.
Each operation deletes one element. If you start with $n$ positions and perform $k$ operations, $n-k$ values remain in order (a subsequence of the original indices). So minimizing operations is the same as maximizing how many elements you can keep while eventually reaching a cool array.
Answer to the counting question: show that an optimal final cool array always corresponds to taking a single path of indices in a certain tree (the next hints pin down which tree and how long that path can be).
Scan indices $1,\ldots,n$ left to right with a stack, using values $a_i$ as keys. When you push index $i$, pop while the stack top has a smaller value than $a_i$; the last popped index becomes the left child of $i$, and the new stack top (if any) gets $i$ as its right child. This is the standard max Cartesian tree: inorder is the original order, and heap order is max-heap.
The global maximum $n$ sits at the root. Every edge connects a larger parent to a smaller child.
Answer to 1.1: the indices you can keep along an optimal strategy correspond to a root-to-leaf path in this tree (one branch at each node).
For a node $u$, let $H[u]$ be one plus the maximum $H$ among its Cartesian-tree children (missing child counts as $0$). Process values $v=1,2,\ldots,n$ in increasing order: at $u=\mathrm{pos}[v]$, both children (if present) have larger values, so their $H$ is already known.
Then $H[u]=1+\max(H[\text{left}],H[\text{right}])$. Intuitively, $H[u]$ is the number of vertices on the longest downward path starting at $u$ inside the subtree.
Why this matches 1.1: the longest root-to-leaf path has length $H[\mathrm{pos}(n)]$ (in vertices).
You must delete everything not on that longest path, so
$$ \text{minimum operations}=n-H[\mathrm{pos}(n)]. $$Implement the stack in $O(n)$, then the value loop in $O(n)$.
You still want the length $L$ of the longest root-to-leaf path in the max Cartesian tree (equivalently, the largest number of indices you can keep). Approach 2 never stores the tree; it computes the same $L$ with two linear scans.
Fix an index $i$ and imagine $a_i$ is the maximum on the path you care about (the “apex” of a mountain in value space). The path descends to smaller values on both sides along the inorder order.
Sweep $i=1,\ldots,n$. Maintain a stack of indices with strictly increasing values (pop while $a_i$ is larger than the stack top’s value). After pops, if the stack is empty, set $\mathrm{dpl}[i]=1$; otherwise $\mathrm{dpl}[i]=\mathrm{dpl}[\text{stack top}]+1$.
Interpretation: $\mathrm{dpl}[i]$ is the length of the downward walk from the left boundary toward $i$ along Cartesian-tree parent pointers / “next greater to the left” structure—without building the tree.
Sweep $i=n,\ldots,1$ with the same stack rule. Define $\mathrm{dpr}[i]$ analogously. Symmetrically, it measures the chain length coming from the right.
For the true global maximum at position $\mathrm{pos}(n)$, the full root-to-leaf path through that vertex has length $\mathrm{dpl}[p]+\mathrm{dpr}[p]-1$ (the apex is counted twice if you add).
Take
$$ L=\max_i\bigl(\mathrm{dpl}[i]+\mathrm{dpr}[i]-1\bigr). $$Then print $n-L$. Two stacks, two passes, $O(n)$ time.
In any subarray $[L,R]$, the largest value in that range is unique (values are distinct). Any root-to-leaf path in the Cartesian tree that visits an index in $[L,R]$ must pass through that maximum (it is the root of the induced subtree on those indices).
So the longest path length $\mathrm{go}(L,R)$ satisfies: if $L=R$, return $1$; otherwise let $p$ be the index of $\max(a_L,\ldots,a_R)$, then
$$ \mathrm{go}(L,R)=1+\max\bigl(\mathrm{go}(L,p-1),\mathrm{go}(p+1,R)\bigr) $$(treat empty ranges as absent / zero contribution). This is exactly the Cartesian-tree height, but written recursively.
Naively finding $p$ in $[L,R]$ costs $O(\text{length})$, which is too slow overall. Keep the pairs $(a_i,i)$ in a range-max segment tree (or sparse table) so you can get $\arg\max$ on any interval in $O(\log n)$.
Memoizing $\mathrm{go}(L,R)$ is optional: each index becomes a segment maximum exactly once along the recursion, so total work is $O(n\log n)$ with a segment tree.