挖油

在线段上从左到右有编号为 $0,1,\ldots,n,n+1$ 的点，其中点 $1$ 到点 $n$ 可以钻井。

存在一个未知整数 $x$ ，满足 $0\le x\le n$ 。对于每个可钻井点 $i$ ，点 $i$ 有油当且仅当 $i\le x$ 。选择点 $i$ 钻井需要花费 $t_i$ 的时间，钻井后会得知该点是否有油。你可以根据此前的钻井结果，决定下一次钻井的位置。

请设计一种钻井策略，使得无论 $x$ 取何值，都能确定 $x$ ，并最小化确定 $x$ 所需总时间的最坏值。输出这个最小的最坏总时间。

输入格式

第一行包含一个整数 $n$ 。

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

输出一行一个整数，表示最坏情况下确定 $x$ 所需的最少时间。

4
8 24 12 6

本题题面与测试数据整理自 BZOJ。

4
8 24 12 6