P5774 [JSOI2016] Virus Infection

A severe Jebola virus outbreak has occurred in a remote border town of JOSI, and many people are infected and in critical condition. Computer scientist JYY has urgently developed a Jebola vaccine using the latest algorithm and rushes to the disaster area to treat patients. There are $N$ towns with Jebola outbreaks. Because these towns are located on the border, they are connected only by one long straight road. For convenience, we number the towns from $1$ to $N$ in the order along the road. JYY will arrive at town $1$ early on the first day. Initially, in town $i$, there are $a_i$ patients infected with the Jebola virus. Each day, JYY may choose one of the following: 1. Spend one day to completely cure all Jebola patients in the town where JYY currently is. On this day, no patients will die. 2. Spend one day to travel to an adjacent town. At the start of a day, if there are $k$ Jebola patients in a town, then by the end of that day, these $k$ patients will infect another $k$ healthy villagers in that town and then die. Therefore, for town $i$, as long as its outbreak has not been completely eliminated by JYY, every day there will be $a_i$ villagers who die. JYY wants to take actions so that when the epidemic is completely eliminated overall, the total number of villagers who die is as small as possible. To achieve this, JYY sometimes will arrive at a town but not treat the villagers. If such behavior is not restricted, it often leads to even more serious consequences. Consider this situation: suppose when JYY first arrives at town $i$, he does not treat anyone and goes directly to another town. Because the people in town $i$ are desperate to survive, once JYY moves in the direction closer to town $i$, the villagers of town $i$ will think JYY is coming to save them, and they will have great hope. Later, if JYY turns around again and moves in the direction farther away from town $i$, the villagers of town $i$ will fall into despair due to huge disappointment. To avoid this, JYY sets the following rule for his trip: Suppose JYY enters town $i$ and leaves immediately on the second day (and the outbreak in town $i$ is not cured). If on some later day, JYY travels from town $j$ to town $k$ and satisfies $|k-i| \lt |i-j|$, then in the days after that JYY may only move toward town $i$ until he reaches town $i$ and immediately cures the patients there. While traveling toward town $i$, JYY may choose to cure the outbreaks in towns he passes through. For example, if JYY has the following schedule: Day 1: travel from town $1$ to town $2$. Day 2: travel from town $2$ to town $3$. Day 3: cure town $3$. Day 4: travel to town $2$. At this time, for the next three days, JYY has only one possible choice: Day 5: cure town $2$. Day 6: travel to town $1$. Day 7: cure town $1$. JYY wants to know, before all towns are cured, at least how many villagers will die from Jebola.

The first line contains a positive integer $N$. The next line contains $N$ integers, which are $a_1,a_2,...,a_N$.

Output one line with one integer, representing the number of villagers who will die under the optimal schedule.

**Sample Explanation** We use $C(k)$ to denote curing town $k$, and $i \rightarrow j$ to denote traveling from town $i$ to town $j$. Using commas to separate the plan for each day, the optimal strategy in the sample is: $1 \rightarrow 2 , C(2),2 \rightarrow 3 , 3 \rightarrow 4 , C(4) , 4 \rightarrow 3 , C(3) , 3 \rightarrow 2 , 2 \rightarrow 1 , C(1) , 1 \rightarrow 2 , 2 \rightarrow 3 , 3 \rightarrow 4 , 4 \rightarrow 5 , 5 \rightarrow 6 , C(6) , 6 \rightarrow 5 , C(5)$; The whole process takes $18$ days. ------ **Constraints** For $10\%$ of the testdata, $N \le 10$. For $30\%$ of the testdata, $N \le 20$. For $50\%$ of the testdata, $N \le 60$. For $100\%$ of the testdata, $1 \le N \le 3000$, $1 \le a_i \le 10^9$. Translated by ChatGPT 5