Let \(f(A_1, \cdots, A_N)\) be the answer to this problem. Note that the arguments of \(f\) are not necessarily distinct and not necessarily sorted.

Without loss of generality, consider the case where \(A_1 = \min(A_i)\). If there exists \(2 \leq i\) such that \(A_i = A_1\), the answer is obviously \(A_1\).

Otherwise, \(f(A_1, \cdots, A_N) = A_1 + f(A_1, A_2-A_1, \cdots, A_N-A_1)\) holds. In other words, if we reduce the width of jumps \(A_i\) (except \(A_1\)) by \(A_1\) and consider movement at coordinates \(\geq A_1\), the remaining cost equals \(f(A_1, A_2-A_1, \ldots, A_N-A_1)\).

This can be shown as follows: First, take an arbitrary optimal solution for \(f(A_1, \cdots, A_N)\). In this optimal solution, consider the moment when we step on a coordinate \(x\) smaller than \(A_1\). In general, if there’s a movement \(p \to x \to q\) (\(x < p,q\)), we can change it to \(p \to x \to x+A_1 \to x \to q\). Meanwhile, in a world where all jump widths are reduced by \(A_1\), we can perform the operation \(p \to x+A_1 \to q\). By establishing this correspondence, we obtain a solution that doesn’t step on coordinates smaller than \(A_1\), but with jump widths \(A_1\) smaller. (If there was a jump of width \(A_i\) at coordinates \(\geq A_1\), we can simply decompose it into two jumps of widths \(A_i-A_1\) and \(A_1\))

Conversely, if there’s a jump of width \(A_i-A_1\) at coordinates \(\geq A_1\), we can convert it to two jumps of widths \(A_i\) and \(A_1\) at coordinates \(\geq 0\).

This proves the equation about \(f\) presented initially. Now we use this to actually compute the value of \(f\). As long as \(A_1\) remains \(\min(A_i)\), we can perform consecutive operations together. We call this series of operations a “stage”. Since each stage takes \(O(N)\) time, we just need to evaluate the number of stages.

Consider the value of \(\min(A_i)\). Suppose initially \(\min(A_i) = X\), and after one stage \(\min(A_i) = Y\). After processing another stage, we have \(\min(A_i) \leq Y\) and \(\min(A_i) \leq X-Y\). This means that after \(2\) stages, the value of \(\min(A_i)\) is necessarily halved or less. Therefore, the number of stages is \(O(\log \max(A_i))\).

Thus, this problem can be solved in \(O(N \log \max(A_i))\) time.

Solution Example