给出一条线段，在左端点0与右端点n+1之间有n个点，若存在一个点x(x∈0..n)，使得点0到点x均是可行的，点x+1到点n+1均是不可行的，那么我们可以使用二分法在O(logn)次操作中求出x。
现在问题有些不一样了，判断点i是否可行需要t_i时间，求一最优策略，使得在最坏情况下求出x的时间最少。
注意，此时二分法并不一定是最优方法。

因版权问题，题目已隐藏。如有需要请私下联系root或nodgd。

第一行一个整数n
第二行n个整数，表示判断点i是否可行的时间。

一个整数，表示最坏情况下最少所需时间。

对于30%的数据 n<=600
对于60%的数据 n<=1300
对于100%的数据 n<=2000, t[i]<=10⁶