电路检修

线路上依次有 $n$ 个检测点。线路可能完全没有故障，也可能存在一个故障起点 $s$ ，其中 $1\le s\le n$ 。若故障起点为 $s$ ，则编号为 $s,s+1,\ldots,n$ 的检测点均发生故障，而编号小于 $s$ 的检测点均正常。

检测第 $i$ 个点需要花费 $a_i$ ，并可以得知该点是否发生故障。后续检测的点可以根据此前的检测结果进行选择。

请设计一种检测策略，使得在任何可能的状态下，都能唯一确定故障起点 $s$ ；如果整条线路没有故障，也必须能够确定这一情况。

一个检测策略的代价，定义为所有可能状态中检测费用总和的最大值。求检测策略代价的最小可能值。

输入格式

第一行包含一个整数 $n$ ，表示检测点的数量。

第二行包含 $n$ 个整数 $a_1,a_2,\ldots,a_n$ ，表示检测各点所需的费用。

输出一个整数，表示最坏情况下检测费用总和的最小值。

4
8 24 12 6

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

4
8 24 12 6