棍子中點切割 (AP325 P-1-3)

有一台切割棍子的機器，每次將一段棍子送入此台機器時，機器會偵測棍子上標示的可切割點，然後計算出最接近中點的切割點，並於此切割點將棍子切割成兩段，切割後的每一段棍子都會被繼續送入機器進行切割，直到每一段棍子都沒有切割點為止。請注意，如果最接近中點的切割點有二，則會選擇座標較小的切割點。每一段棍子的切割成本是該段棍子的長度，輸入一根長度 \(L\) 的棍子上面 \(N\) 個切割點位置的座標，請計算出切割總成本。

輸入格式

第一行有兩個正整數 \(N\) 與 \(L\)。第二行有 \(N\) 個正整數，依序代表由小到大的切割點座標 \(p_1, p_2, \ldots, p_N\)，數字間以空白隔開；座標的標示方式是以棍子左端為 \(0\)，而右端為 \(L\)。

限制

• \(1 \le N \le 5 \times 10^4\)，\(L < 10^9\)。
• \(0 < p_1 < p_2 < \cdots < p_N < L\)，也就是切割點兩兩不同，且不在棍子的兩端。

輸出格式

輸出切割總成本。

評分說明

每筆計分測資獨立計分，每筆 5 分，共 100 分；範例不計分。

範例輸入

4 10
1 2 4 6

範例輸出

22

範例說明

第一次會切割在座標 \(4\) 的位置，切成兩段 \([0, 4]\)、\([4, 10]\)，成本 \(10\)； \([0, 4]\) 切成 \([0, 2]\) 與 \([2, 4]\)，成本 \(4\)； \([4, 10]\) 切成 \([4, 6]\) 與 \([6, 10]\)，成本 \(6\)； \([0, 2]\) 切成 \([0, 1]\) 與 \([1, 2]\)，成本 \(2\)； 總成本 \(10 + 4 + 6 + 2 = 22\)。

題目來源

本題出自中正大學吳邦一教授所著《AP325－從 APCS 實作題檢測三級到五級》（v1.5）第 1 章 P-1-3，第 20 頁；經作者同意於 AACPOJ 免費公開。教材下載：AP325 講義（Google Drive）；Python 版：AP325-Python（HackMD）。