1858: 怎么了，你累啦？

内存限制：128 MB 时间限制：1.000 S
评测方式：文本比较 命题人：
提交：65 解决：6

题目描述

众所周知，旅行是极其消耗 原能的，所以旅行者的原能已经花费完啦，但是旅行者偶然发现了一个原石场， 同样原石能够兑换成原能， 但原石会不断缩水，极其不稳定，所以当原石被串在一根原绳上时， 当紧挨着的两块原石都比中间的一些原石能值高，中间的原石就会缩水消失，同样当中间的消失后两边的原石就会紧挨在一起，现在旅行者有一串原石，其中头尾不相连，这串原石缩水后旅行者能得到多少原石。

输入

第一行 一个整数 n
接下来一行， n 个整数 第 i个整数xi表示 第i块原石的原石值， 0 <= xi <= 1e9， n <= 4e6;  

输出

剩余原石能量值和

样例输入 复制 

5
1 3 2 4 5

样例输出 复制 

13

提示

第一块原石和最后一块不会消失


样例解释

原石消失后变为 ：

1 3 4 5

能量和为 13