Description

A severe Jebola virus outbreak has occurred in the remote towns of JOSI. Many people are in critical condition. Computer scientist JYY has urgently developed a Jebola vaccine and is rushing to the disaster area to treat the patients.

There are $N$ towns affected by the Jebola outbreak. Because these towns are located in a remote border area, they are connected by a single long, straight road. For convenience, we label these towns from $1$ to $N$ in the order they are connected by the road.

JYY arrives at town $1$ on the first day. Initially, there are $a_i$ patients infected with the Jebola virus in town $i$.

Each day, JYY can choose to: 1. Spend one day thoroughly curing all Jebola patients in the town where JYY is currently located. On this day, no patients will die. 2. Spend one day traveling to an adjacent town.

At the beginning of each day, if there are $k$ Jebola patients in a town, then by the end of that day, these $k$ patients will infect $k$ healthy villagers in that town, and those $k$ patients will die. Therefore, for town $i$, as long as the town has not been completely cleared of the epidemic by JYY, $a_i$ villagers will die every day.

JYY hopes to adopt a strategy to eliminate the epidemic such that the total number of villagers who die is minimized. To achieve this goal, JYY sometimes chooses to arrive at a town but does not perform any treatment on the villagers. If this behavior is not restricted, it often leads to more serious consequences.

Consider this situation: Suppose JYY arrives at town $i$ for the first time, does not perform treatment, and immediately proceeds to another town. Because the people in town $i$ are desperate for survival, once JYY moves in a direction closer to town $i$, the villagers in town $i$ will think JYY is coming to save them, creating great expectations. If JYY subsequently turns and moves in a direction away from town $i$, the villagers in town $i$ will fall into despair due to the immense disappointment.

To avoid this situation, JYY has set the following rules for his itinerary: Suppose JYY enters town $i$ and leaves immediately on the next day (the epidemic in town $i$ is not cured). If on a subsequent day, JYY travels from town $j$ to town $k$, and satisfies $|k - i| < |j - i|$, then in the following days, JYY must move towards town $i$ until he reaches town $i$ and immediately cures the patients there. In the process of heading to town $i$, JYY can choose to cure the epidemic in the towns he passes through.

For example, if JYY has the following itinerary: Day 1: From town 1 to town 2; Day 2: From town 2 to town 3; Day 3: Cure town 3; Day 4: Move to town 2. At this point, JYY has only one choice for the next three days: Day 5: Cure town 2; Day 6: Move to town 1; Day 7: Cure town 1.

JYY wants to know the minimum number of villagers who will die before all towns are cured.

Input

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

Output

Output a single integer representing the minimum number of villagers who will die under the optimal itinerary.

Constraints

• For 10% of the data, $N \le 10$;
• For 30% of the data, $N \le 20$;
• For 50% of the data, $N \le 60$;
• For 100% of the data, $1 \le N \le 3000$, $1 \le a_i \le 10^9$.

Examples

Input 1

6
40 200 1 300 2 10

Output 1

1950

Note

We use $C(k)$ to denote curing town $k$, and $i \to j$ to denote moving from town $i$ to town $j$. Separating each day's itinerary with semicolons, the optimal strategy in the example is: $1 \to 2$; $C(2)$; $2 \to 3$; $3 \to 4$; $C(4)$; $4 \to 3$; $C(3)$; $3 \to 2$; $2 \to 1$; $C(1)$; $1 \to 2$; $2 \to 3$; $3 \to 4$; $4 \to 5$; $5 \to 6$; $C(6)$; $6 \to 5$; $C(5)$. The entire process takes 18 days.