救治新冠肺炎患者
题号：NC205464
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

公元2020庚子年初，2019-nCoV病毒在全球爆发，全世界人民共同抗击疫情，某国成为了重灾区，人们生命受到了前所未有的威胁，医学专家与计算机专家携手抗击疫情，很快研究开发出来治疗新冠肺炎的特效药和疫苗，现在急需专家组携带医疗物资十万火急前往该国灾区救治患者。
假设该国一共有n个城市爆发了2019-nCoV病毒，这些城市链接成了一条线，编号从1到n，在第 i 个城市中有 ai 名患者感染了病毒，专家组第一天凌晨到达1号城市。
每天清晨专家组可以选择:
1.花费一天治愈该城市所有患者. 2.花费一天在路上前往一个相邻的城市.
当每天开始时如果某个城市里有m名患者，那么这天结束时这m个患者会感染另外m个健康的人，并且开始的这m个患者会在当天死去.
专家组要制定一种方案，使因为2019-nCoV病毒死去的人的总数最少。
如果专家组达到 i 城市，且并未治愈该城的疫情，那么当专家组从j城市前往k城市时，且|i-k|<|j-k|，此时专家组必须返回 i 城并立即治愈所有感染者(如果i城的人们看见专家组来救他们如果专家组再次远离他们的话他们会绝望的，所以必须前往救援)，前往i城市时沿途城市是否治愈患者专家组可以自行抉择。
请你编程帮助专家组完成这个任务。

输入描述:

输入一行一个正整数n(1<=n<=3000).
接下来一行n个整数，分别表示a1,a2,a3...an.(1<=ai<=1e9)

输出描述:

输出一行一个整数,最优安排时死亡的人的总数.
示例1

输入

复制 
6
40 200 1 300 2 10

输出

复制 
1950

说明

最优策略:1到2,治愈2,2到3,3到4,治愈4,4到3,治愈3,3到2,2到1,治愈1,1到2,2到3,3到4,4到5,5到6，治愈6,6到5,治愈5