出處: 2021 NPSC網際網路程式設計大賽高中組網路賽pG

這天，你在趕著去參加 NPSC (National Party of Super Cat) 的路上，就在你快抵達會場時，⼀隻巨⼤的貓貓神突然降臨在你的⾯前。

「⽤最⼩的花費，刪除掉整個陣列吧！」

這麼說著的貓貓神拿出了⼀個 \(N\) 個元素的陣列並擺在你眼前，祂向你說明了規則：

• 你每次可以選擇⼀對相鄰的元素對將其刪除，並花費「兩個元素的數值最⼩值」。
• 刪除後，陣列將會合併起來。
• 你必須執⾏ \(\frac{N}{2}\) 個操作來將整個陣列刪除，並且所有操作的花費和要最⼩。

不快⼀點完成貓貓神的任務的話，你就⾒不到可愛的貓咪們了，⽽經由你苦苦哀求後，貓貓神決定讓你找出最⼩的花費和即可，快點完成祂的任務並投向貓咪的懷抱吧！

輸入格式

輸⼊的第⼀⾏有⼀個正整數 \(N\)，代表陣列的⼤⼩。
第⼆⾏有 \(N\) 個以空格分開的正整數 \(a_1, a_2, . . . , a_N\)，代表陣列的內容，\(a_i\) 代表第 \(i\) 個元素的數值。

• \(1 ≤ N ≤ 2 × 105\)
• \(N\) 是偶數
• \(1 ≤ a_i ≤ 109\)

輸出格式

輸出⼀⾏⼀個正整數，代表欲將整個陣列刪除的最⼩花費。

範例輸入1

4
1 3 2 4

範例輸出1

3

範例輸入2

8
1 9 7 6 8 7 6 3

範例輸出2

16

範例輸入3

6
3 1 4 1 5 9

範例輸出3

5