Minimizing Variance in a Swappable Sequence

You are given a non‐decreasing sequence of n positive integers

\[1 \le a_1 \le a_2 \le \cdots \le a_n\]

You are allowed to perform the following operation any number of times:

Select any index i with \(1 < i < n\) and change \(a_i\) to

\[ a_i \leftarrow a_{i-1} + a_{i+1} - a_i. \]

This operation essentially swaps the adjacent differences. In other words, if we define \(d_i=a_{i+1}-a_i\), then an operation performed on \(a_i\) swaps \(d_{i-1}\) and \(d_i\) (while keeping the endpoints \(a_1\) and \(a_n\) fixed).

Your task is to minimize the variance of the sequence after performing an arbitrary number of operations. The variance is defined as

[ D = \frac{1}{n}\sum_{i=1}^{n}(a_i-\bar{a})^2, \quad \text{where} \quad \bar{a}=\frac{1}{n}\sum_{i=1}^{n}a_i. ]

Output the value of \(n^2 \cdot D\) for the sequence with minimum variance that can be achieved by reordering the internal differences optimally.

Observation: Since the operations only swap the differences \(d_i\) (with \(\sum_{i=1}^{n-1} d_i=a_n-a_1\) fixed) and do not affect the endpoints, the optimal sequence is the one whose differences are distributed as evenly as possible. In other words, if we let \(T=a_n-a_1\) then letting \(q=\lfloor T/(n-1) \rfloor\) and \(r=T \bmod (n-1)\), the optimal (feasible) sequence \(b_1,\dots,b_n\) is given by

[ b_1=a_1,\quad b_{i}=a_1+(i-1)\cdot q + \left\lfloor \frac{(i-1), r}{n-1} \right\rfloor \quad \text{for } i=2,3,\dots,n. ]

The answer to output is then computed as

[ \text{answer} = n^2 \cdot \left(\frac{1}{n}\sum_{i=1}^{n}(b_i-\bar{b})^2\right) = \frac{1}{n}\sum_{i=1}^{n}(n,b_i-S)^2, \quad \text{with } S=\sum_{i=1}^{n}b_i. ]

</p>

Your program should read the input sequence, compute the optimal configuration as described, and output the resulting integer value.

inputFormat

The first line contains an integer n (\(n \ge 3\)). The second line contains n space‐separated positive integers \(a_1, a_2, \dots, a_n\) satisfying \(1 \le a_1 \le a_2 \le \cdots \le a_n\).

outputFormat

Output a single integer: the minimum possible value of \(n^2 \cdot D\), where \(D\) is the variance of the sequence after an optimal sequence of operations.

sample

3
1 2 3

6