If we know that a certain \(H\) value is possible, it’s easy to calculate the total cost needed: it’s \( (\sum_i U_i + D_i) - H \cdot N\). Since we need to minimize the cost, we should try to maximize \(H\), and we note that the decision function on whether a certain \(H\) is possible is monotonic (if a solution exists for \(H = x \ge 1\), it exists for \(H = x - 1\)). Also note that an upper bound on \(H\) is \(H \le \min_i U_i + D_i\).

Now let’s implement the decision function for a fixed \(H\). Let \(U'_i\) represent the final length of the upper tooth at position \(i\). Note that there are two constraints that could apply for each \(U'_i\):

• \(\max (0, H - D_i) \le U'_i \le \min(H, U_i)\)
• For \(i > 1\), \(U'_{i-1} - X \le U'_i \le U'_{i-1} + X\)

If we let \(l_i\) and \(r_i\) represent the lower and upper bounds on \(U'_i\), it can be seen that:

• \(l_i = \max (0, H - D_i, l_{i-1} - X)\)
• \(r_i = \min (H, U_i, r_{i-1} + X)\)

Thus the decision function should accept \(H\) if and only if \(l_i \leq r_i\) for all \(i\).

Time complexity: \(O(N \log \min_i U_i + D_i)\)