次の問題が解ければよいです。

• 数列 \(A\) がある。マージ操作と挿入操作を自由な順番で行って \(A\) の長さを \(1\) にしたい。挿入操作を最小で何回行う必要があるか？

\(A\) をランレングス圧縮した列を \((v_1, c_1), (v_2, c_2), \dots, (v_K, c_K)\) とします。(\(v_i\) は値で \(c_i\) は頻度)
この時、次の一連の操作を行うのが最適です。

• \(v_i\) が最小であるものをどれか 1 つ選んで \((v_i, c_i)\) とする。
• \(c_i\) が奇数の場合は挿入操作を用いてその箇所に \(v_i\) を追加して \(c_i\) に \(1\) 加算する。
• その後、\(v_i\) に対して左にある要素から順にマージ操作を \(\frac{c_i}{2}\) 回行い \(v_i\) を全て \(v_i + 1\) に変化させる。

(証明) \(c_i = 1\) の場合を考えます。まず、挿入操作を行った直後は直前に挿入した値とマージする操作を行うとして問題ないので、挿入操作はインクリメントする操作に読み替えることができます。\(v_i\) の前後は \(v_i\) よりも大きい要素があるか何もないかで、これは操作によって変わらないので \(v_i\) は必ずインクリメントする必要があるので行って問題ないです。
\(c_i \geq 2\) かつ \(c_i\) が偶数の場合を考えます。各要素について「左の要素とマージする」「右の要素とマージする」「インクリメントする」のどれを選ぶかを決めて、マージおよびインクリメントを直ちに行うと、インクリメントする要素の個数を \(x\) として \(x+\frac{c_i-x}{2} = \frac{c_i+x}{2}\) 個の \(v_i+1\) が生成されます。しかし \(x\geq 2\) の場合、\(v_i\) に対して左にある要素から順にマージ操作を \(\frac{c_i}{2}\) 回行ったあとに \(\frac{x}{2}\) 回 \(v_i+1\) を挿入する方が挿入操作の回数が少なく済むので、\(x \geq 2\) の場合は考えなくてもよいです。よって全ての要素にマージ操作を作用させるのが最適であるとわかります。
\(c_i \geq 2\) かつ \(c_i\) が奇数の場合も同様の議論が回り、インクリメントする要素は高々 \(1\) 個で良いことがわかります。以上により証明が完了しました。(証明終わり)

上記のシミュレーションは愚直に行うと低速ですが、 std::set を適切に用いれば \(\mathrm{O}(N \log N)\) で計算することができます。さらに、もう少し考察を進めると、\(A_i \gt A_{i+1} = A_{i+2} = \dots = A_{j-1} \lt A_j\) という形があったときに中央部分をマージ操作や挿入操作を用いて \(A_i\) か \(A_j\) のどちらかに揃えることが最適であることが証明できるので、stack を用いて \(\mathrm{O}(N)\) で解くこともできます。どちらの方法を選んでも十分高速です。