Token Aggregation on a Cycle

We are given a cycle of n vertices numbered from 1 to n where vertex 1 and vertex n are adjacent. Each vertex i carries an integer weight a_i (which you can think of as a number of tokens). You wish to achieve a configuration in which there is exactly one vertex x (1 ≤ x ≤ n) for which a_x ≠ 0 (that is, all tokens are concentrated on vertex x).

The allowed procedure is as follows:

1. Choose a target vertex x where eventually you want all tokens to be. This choice of x is fixed thereafter.
2. Perform a number of operations. In each operation you choose any vertex y (1 ≤ y ≤ n), and then update its weight by doing
   \(a_y \gets a_y - 1\) and, simultaneously, among the two neighbors of vertex y (note that the cycle means that vertex 1 and vertex n are adjacent) you add one token to one of them, chosen uniformly at random.

Notice that the total number of tokens remains invariant. In fact, each operation moves one token from one vertex to one of its two neighbors at random. The goal is to aggregate all tokens to the fixed vertex x so that, in the final configuration, only a_x is nonzero.

Under an optimal strategy (i.e. by choosing the target vertex and the sequence of operations optimally) it turns out that the expected number of operations is the sum of the individual expected operations required to drive each token from its initial position to the target vertex. In other words, if a vertex i (other than x) starts with a_i tokens and the minimum circular distance (along the cycle, i.e.
\(d(i,x)=\min(|i-x|,n-|i-x|)\)) is used then the expected number of operations needed to bring a single token from vertex i to vertex x is

[ f(d)=d\times (n-d)]

This formula can be verified on small examples. Hence, if you choose vertex x as the target, the expected number of operations is

[ E(x)=\sum_{\substack{i=1\i\ne x}}^{n} a_i\times \Bigl(\min(|i-x|,n-|i-x|)\cdot (n-\min(|i-x|,n-|i-x|))\Bigr). ]

Your task is to choose the optimal vertex x so that E(x) is minimized, and output that minimum expected number of operations.

inputFormat

The first line contains a single integer n (the number of vertices in the cycle).
The second line contains n integers a₁, a₂, …, a_n representing the initial token counts at each vertex.

outputFormat

Output a single integer — the minimum expected number of operations under the optimal strategy.

sample

3
1 2 3

6