Jebola Epidemic Minimization

In the border town of JOSI, a severe outbreak of the Jebola virus has occurred. Many villagers have been infected and are in critical condition. The computer scientist JYY has developed a vaccine using a state‐of‐the‐art algorithm and rushes to the affected areas along a long straight highway.

There are N villages suffering from the Jebola epidemic. The villages are arranged in order along the highway and numbered from 1 to \(N\). JYY arrives in village 1 early on the first day.

Initially, village \(i\) has \(a_i\) infected patients. Each day, every village that has not yet been cured suffers additional deaths. In detail, at the beginning of a day, if a village has \(k\) patients, then by the end of that day the infection causes another \(k\) healthy villagers to get infected and die. In other words, as long as a village is not cured, it loses \(a_i\) villagers per day.

Each day, JYY can choose one of two actions:

1. Spend the day in the current village to cure it completely (in which case no deaths occur in that village on that day).
2. Spend the day traveling to an adjacent village.

However, to prevent disastrous consequences from delaying treatment, there is an additional rule. If JYY enters village \(i\) and on the very next day leaves without treating it, then later if he ever reverses direction—that is, if on some day he moves from village \(j\) to village \(k\) with \(|k-i| < |j-i|\)—he is forced, for all subsequent days, to head directly toward village \(i\). He must continue in that direction until he reaches village \(i\) and immediately cures it. (During the journey back, he is allowed to treat other villages if he wishes.)

Observing the rules carefully, it is optimal for JYY to cure a village immediately upon his arrival to avoid triggering the forced return mechanism. Thus, the best strategy is:

• Cure village 1 on day 1.
• For each subsequent village \(i\) (with \(i \ge 2\)): spend one day traveling from village \(i-1\) to village \(i\) and then the next day curing village \(i\).

Under this strategy, note that when village \(i\) is cured, it has already suffered deaths on every day before its cure. Since the cure for village \(i\) happens on day \(2(i-1)+1\), the village endures deaths for \(2(i-1)\) days. Therefore, the total number of deaths is given by:

[ Total\ Deaths = \sum_{i=2}^{N} 2(i-1)a_i. ]

inputFormat

The first line contains an integer \(N\) (\(1 \le N \le 10^5\)), the number of villages.

The second line contains \(N\) space-separated integers \(a_1, a_2, \ldots, a_N\) where \(a_i\) represents the number of infected patients in village \(i\).

outputFormat

Output a single integer, the minimum total number of villagers who will have died by the time all villages have been cured.

sample

1
5

0