$XHM$是圣玛格诺利亚共和国的一个秘密警察。

这周，怹接到秘密任务X，需要搞定坏蛋K。

$XHM$的情报网可以看作一根线。怹处在最左边，最右边的是坏蛋，夹在中间是很多层的线人。$XHM$可以买通其中一些线人，买通每个线人的价格是不同的。

搞定一个坏蛋的方法是：存在一种收买线人方案，除了XHM和坏蛋（起点和终点外），路径上每两个相邻的节点对中（每一对相邻的线人之间），总有一个节点被买通了。

举例来说，在路径$XHM \rightarrow A \rightarrow C \rightarrow K$，为了搞定坏蛋K，有两种买通方法，买通A或者买通C。

$XHM$已经计算了一天一夜，但是她碍于有限的脑容量实在想不出搞定坏蛋K最低价格，快帮她算算，这样她可以向圣玛格诺利亚报预算。

第一行输入$n$，代表节点数量。$(1\leqslant n \leqslant 2\times 10 ^ 6)$

后续一行，输入$n$个数字$a_i$，代表买通i节点的价格。$(1\leqslant a_i \leqslant 1\times 10 ^ 2)$

显然，开头（XHM自己）和结尾（坏蛋）的$a_i$是不需要被收买的。

输出一个数字，XHM向圣玛格诺利亚申请预算价格。

可以考虑DP的方法，思考路径上0-1状态之间如何最优的转移。