题号：NC22616
时间限制：C/C++/Rust/Pascal 3秒，其他语言6秒
空间限制：C/C++/Rust/Pascal 128 M，其他语言256 M
64bit IO Format: %lld
时间限制：C/C++/Rust/Pascal 3秒，其他语言6秒
空间限制：C/C++/Rust/Pascal 128 M，其他语言256 M
64bit IO Format: %lld
题目描述
小y得到了一摞n张纸牌，每张纸牌上面都写着一个数字。
现在小y要把这摞纸牌分成两摞。
分牌的方法如下：
假设最开始的那摞纸牌为A，要分成B，C两摞。
他每次会拿起A中最上面的一张纸牌，将其放到B或C的最上面。直到A中的纸牌被取完。(显然，取到的牌的顺序是一定的)。
对于分成的B摞和C摞纸牌，其中的每张纸牌的代价都是它和下面所有的纸牌中，所写数字最大的那个纸牌上所写的数字。
举个例子:
假如分成的B摞纸牌从下往上的纸牌依次是：2,4,1,3,5
那么这5张纸牌的代价依次是:2,4,4,4,5。
C摞同理
他想要找到一种方法使得分成的两摞纸牌的代价和最小，你只需输出这个代价即可。
现在小y要把这摞纸牌分成两摞。
分牌的方法如下：
假设最开始的那摞纸牌为A，要分成B，C两摞。
他每次会拿起A中最上面的一张纸牌，将其放到B或C的最上面。直到A中的纸牌被取完。(显然，取到的牌的顺序是一定的)。
对于分成的B摞和C摞纸牌，其中的每张纸牌的代价都是它和下面所有的纸牌中，所写数字最大的那个纸牌上所写的数字。
举个例子:
假如分成的B摞纸牌从下往上的纸牌依次是：2,4,1,3,5
那么这5张纸牌的代价依次是:2,4,4,4,5。
C摞同理
他想要找到一种方法使得分成的两摞纸牌的代价和最小，你只需输出这个代价即可。
输入描述:
第一行一个正整数n，表示纸牌的个数。
第二行n个用空格隔开的非负整数，第i个数字表示从上往下数第i张纸牌上面的数字。
输出描述:
一行一个整数，表示最小代价。