\(f(A_1,\cdots,A_N)\) をこの問題の答えとします． ただし，\(f\) の引数は必ずしもdistinctではなく，またソートされているとも限らないものとします．

一般性を失わず，\(A_1 = \min(A_i)\) のケースを考えます． もし，\(A_i=A_1\) となる \(2 \leq i\) が存在するなら，答えは明らかに \(A_1\) です．

そうでない時，\(f(A_1,\cdots,A_N)=A_1+f(A_1,A_2-A_1,\cdots,A_N-A_1)\) が成立します． 言い換えると，\(A_1\) を除くジャンプ \(A_i\) の幅を \(A_1\) だけ減らしたあと，座標 \(A_1\) 以上での移動を考えると，元の問題と同じ答えになります．

これは次のように示せます． まず \(f(A_1,\cdots,A_N)\) の最適解を任意に取ります． この最適解において，\(A_1\) より小さい座標 \(x\) を踏む瞬間を考えます． 一般に，\(p \to x \to q\) (\(x < p,q\))という動きがあったら，これを \(p \to x \to x+A_1 \to x \to q\) としても構いません． ところで，全部のジャンプの幅を \(A_1\) 減らした世界では，\(p \to x+A_1 \to q\) という操作が行えます． これらを対応させることで，\(A_1\) より小さい座標を踏まない代わりに，ジャンプの幅が \(A_1\) だけ小さい解，というものが得られます． （座標 \(A_1\) 以上で幅 \(A_i\) のジャンプがあった場合，これは単に幅 \(A_i-A_1\), \(A_1\) の \(2\) 回のジャンプに分解すればよいです）

また逆に，座標 \(A_1\) 以上で幅 \(A_i-A_1\) のジャンプがあった場合，これを座標 \(0\) 以上の幅 \(A_i\), \(A_1\) の \(2\) 回のジャンプに変換することもできます．

これで最初に提示した \(f\) に関する等式が証明できました． あとはこれを用いて実際に \(f\) の値を求めます． \(A_1\) が \(\min(A_i)\) であり続ける限り，連続した操作をまとめて行うことができます． この \(1\) 連の操作を”ステージ”と呼びます． \(1\) ステージあたりで \(O(N)\) 時間かかるので，あとはこのステージの回数が評価できればよいです．

\(\min(A_i)\) の値を考えます． まず最初 \(\min(A_i)=X\) だったのが，\(1\) ステージ後に \(\min(A_i)=Y\) になったとします． その後もう \(1\) ステージ処理すると，\(\min(A_i) \leq Y\) かつ \(\min(A_i) \leq X-Y\) となります． つまり，\(2\) ステージ後には必ず \(\min(A_i)\) の値が半分以下になることがわかります．よってステージの回数は \(O(\log \max(A_i))\) です．

よってこの問題は \(O(N \log \max(A_i))\) 時間で解けます．

回答例