4507 . 星冰樂買一送一
Description
知名咖啡店Starburst正在進行一個星冰樂買一送一的活動。最懂的找到店家優惠的Brine當然要去狠狠地喝一波了。
已知Starburst這次買一送一的規則如下：
Starburst的員工Kirito會將n杯星冰樂放成一排，而從左數過來第$i$杯的星冰樂價錢為$S_i$。另外，如果你選擇買其中的某一杯星冰樂，那你可以免費拿走隨意一杯與其相鄰的星冰樂。在你拿完你買的和送的星冰樂之後，架上的星冰樂會自動靠攏把空隙填滿。
想請問Brine最少花多少錢就可以喝到每一杯星冰樂？
Input Format
$n$
$S_1\;S_2\;S_3...S_n$
$1\le n \le 10^6$，且保證$n$為偶數
$1\le S_i \le 10^9$
Output Format
請輸出一個整數，代表Brine要花的錢
Sample Input 1
4
1 4 2 3
1 4 2 3
Sample Output 1
3
Hints
Subtasks
| No. | Testdata Range | Score |
|---|---|---|
| 1 | 0~20 | 100 |
