题目描述

给出一条线段，在左端点 $0$ 与右端点 $n+1$ 间有 $n$ 个点，并且在 $0$ 到 $x$ 之间的所有点都是有油的，在每个点钻井判断是否有油需要时间 $t_i$，求能够知道 $x$ 的最坏情况下最少需要多少时间。

输入格式

第一行包含一个正整数 $n$，如题目描述。

第二行包含 $n$ 个整数，表示在第 $i$ 个点钻井判断是否有油需要的时间。

输出格式

输出包含一行，最坏情况下最少需要多少时间。

4
8 24 12 6

42

数据规模与约定

对于 $100\%$ 的数据，$1\le n\le2\times 10^3$，$1\le t_i\le 10^6$。

题目来源

2011福建集训