#3156. 防御准备

内存限制:512 MiB 时间限制:10 Sec

题目描述

输入格式

第一行为一个整数N表示战线的总长度。

第二行N个整数,第i个整数表示在位置i放置守卫塔的花费Ai

输出格式

共一个整数,表示最小的战线花费值。

样例

样例输入


			


10
2 3 1 5 4 5 6 3 1 2

样例输出


			

18

数据范围与提示



1<=N<=10^6,1<=Ai<=10^9