题目描述

科学馆的电路最近出故障了，zusf 决定进行一次彻底地检修。

为了简化问题，将科学馆的电路看成一条直线，直线上有很多端点。因为某些奇葩的原因，zusf 已经知道电路中出故障的部分一定是从某个端点开始直到末端，最坏的情况就是整条线路从起点开始都有问题。

你现在能使用一种特殊的设备进行检测，检测必须在端点上，每次检测的结果是当前这个端点是否出现故障。由于科学馆的线路年久失修，某些端点检测起来代价非常大，凭借 zusf 对科学馆的了解，现在已经预估出了所有端点的检测代价，你要求出最少代价以精确确定电路故障起始的位置（有可能整条线路都没有问题)。

输入格式

第一行包含一个整数 $n$ ，表示科学馆电路上端点的数目。

第二行包含 $n$ 个整数，第 $i$ 个整数 $a_i$ 表示检测第 $i$ 个端点的代价。

输出格式

一个整数，表示最小代价。

4
8 24 12 6

42

数据规模与约定

对于 $100\%$ 的数据，$1 \le n \le 2000 , 0\le a_i \le 10^6$ 。