The following problem needs to be solved:

• There is a sequence \(A\). We want to reduce the length of \(A\) to \(1\) by performing merge operations and insertion operations in any order. What is the minimum number of insertion operations needed?

Let the run-length encoded sequence of \(A\) be \((v_1, c_1), (v_2, c_2), \dots, (v_K, c_K)\). (\(v_i\) is the value and \(c_i\) is the frequency.)
Then, it is optimal to perform the following series of operations:

• Choose any one with the smallest \(v_i\) and call it \((v_i, c_i)\).
• If \(c_i\) is odd, use an insertion operation to add \(v_i\) at that location and add \(1\) to \(c_i\).
• Then, perform merge operations \(\frac{c_i}{2}\) times from left to right for \(v_i\), changing all \(v_i\) to \(v_i + 1\).

(Proof) Consider the case where \(c_i = 1\). First, immediately after performing an insertion operation, we can perform a merge operation with the previously inserted value, so insertion operations can be interpreted as increment operations. Before and after \(v_i\), there are either elements larger than \(v_i\) or nothing, and this does not change with operations, so \(v_i\) must necessarily be incremented, so there is no problem in doing so.
Consider the case where \(c_i \geq 2\) and \(c_i\) is even. If we decide, for each element, what to choose from “merge with left element”, “merge with right element”, and “increment”, and immediately perform those merge and increment operations, then \(x+\frac{c_i-x}{2} = \frac{c_i+x}{2}\) copies of \(v_i+1\) are generated, where \(x\) is the number of elements to increment. However, when \(x\geq 2\), performing merge operations \(\frac{c_i}{2}\) times from left to right for \(v_i\) and then inserting \(v_i+1\) \(\frac{x}{2}\) times requires fewer insertion operations, so we do not need to consider the case \(x \geq 2\). Therefore, it is optimal to apply merge operations to all elements.
A similar argument applies when \(c_i \geq 2\) and \(c_i\) is odd, and we find that at most one element needs to be incremented. This completes the proof. (End of proof)

The above simulation is slow if performed naively, but can be computed in \(\mathrm{O}(N \log N)\) by appropriately using std::set. Furthermore, with a bit more consideration, when there is a pattern like \(A_i \gt A_{i+1} = A_{i+2} = \dots = A_{j-1} \lt A_j\), it can be proved that it is optimal to align the middle part to either \(A_i\) or \(A_j\) using merge operations and insertion operations, so it can also be solved in \(\mathrm{O}(N)\) using a stack. Either method is sufficiently fast.