• You are given a length-\(n\) integer sequence \(c=(c_1,c_2,\ldots,c_n)\). Perform this operation \(n-1\) times: choose adjacent elements \(c_i,c_{i+1}\) and replace them with \(\max(c_i,c_{i+1})+1\). Find the minimum possible final value of \(c_1\).

It suffices to pick the \(i\) minimizing \(\max(c_i,c_{i+1})\) (breaking ties by taking the smallest \(i\)) and merge those.

Proof:

Let \(F(c)\) denote the minimum possible final value of \(c_1\) when performing operations on an integer sequence \(c\).

The operation can be decomposed into the following:

• Increase the value of any element by \(1\).
• Merge two adjacent equal elements into one element with value increased by \(1\).

First, if two sequences \(a,b\) of the same length satisfy \(a_i \le b_i\) for all \(i\), then \(F(a) \le F(b)\). Also, if a sequence \(a\) contains a sequence \(b\), then \(F(b) \le F(a)\).

For a sequence \(a\), let \(v=\min_i a_i\) be its minimum value. Using the operations described above, we can replace \(x\) consecutive occurrences of the value \(v\) in \(a\) with \(\displaystyle \left\lceil \frac x2\right\rceil\) consecutive values of \(v+1\). We denote this operation by \(\rho\) and the resulting sequence by \(\rho(a)\). Then \(F(a) = F(\rho(a))\).

Proof:

Clearly, \(F(a) \le F(\rho(a))\).

Focusing on each element whose initial value is \(v\), there are only two ways its value can change from \(v\):

• It is merged with an adjacent \(v\) to become a single \(v+1\).
• Its value is increased to \(v+1\).

Fewer remaining elements with value \(v+1\) is better, so it is optimal to merge these \(x\) values as much as possible. Thus, we may replace them with \(\displaystyle \left\lceil \frac x2\right\rceil\) consecutive values of \(v+1\), and this gives us \(F(a) \geq F(\rho(a))\).

By this lemma, if there exist adjacent occurrences of the minimum value, we may merge the leftmost two among them. Considering the fact that if there are no adjacent occurrences of the minimum value, we increase the minimum-valued elements by \(1\), we see that the operation of compressing the sequence while preserving the value of \(F\) coincides with the greedy algorithm.