P7962 [NOIP2021] Variance

Given a non-strictly increasing sequence of positive integers of length $n$: $1 \le a_1 \le a_2 \le \cdots \le a_n$. In each operation, you may choose any positive integer $1 < i < n$ and change $a_i$ to $a_{i - 1} + a_{i + 1} - a_i$. After performing some operations, find the minimum possible variance of the sequence. Output the result of the minimum variance multiplied by $n^2$. The variance is defined as the average of the squared differences between each number and the mean. More formally, the variance is $D = \frac{1}{n} \sum_{i = 1}^{n} {(a_i - \bar a)}^2$, where $\bar a = \frac{1}{n} \sum_{i = 1}^{n} a_i$.

The first line contains a positive integer $n$, and it is guaranteed that $n \le {10}^4$. The second line contains $n$ positive integers, where the $i$-th number is $a_i$. The testdata guarantees that $1 \le a_1 \le a_2 \le \cdots \le a_n$.

Output a single line containing a non-negative integer, which is the minimum variance you can obtain multiplied by $n^2$.

**Sample Explanation #1** For $(a_1, a_2, a_3, a_4) = (1, 2, 4, 6)$, after the first operation, the possible sequence is $(1, 3, 4, 6)$. After the second operation, the new sequence is $(1, 3, 5, 6)$. After that, no new sequence can be obtained. For $(a_1, a_2, a_3, a_4) = (1, 2, 4, 6)$, the mean is $\frac{13}{4}$, and the variance is $\frac{1}{4}({(1 - \frac{13}{4})}^2 + {(2 - \frac{13}{4})}^2 + {(4 - \frac{13}{4})}^2 + {(6 - \frac{13}{4})}^2) = \frac{59}{16}$. For $(a_1, a_2, a_3, a_4) = (1, 3, 4, 6)$, the mean is $\frac{7}{2}$, and the variance is $\frac{1}{4} ({(1 - \frac{7}{2})}^2 + {(3 - \frac{7}{2})}^2 + {(4 - \frac{7}{2})}^2 + {(6 - \frac{7}{2})}^2) = \frac{13}{4}$. For $(a_1, a_2, a_3, a_4) = (1, 3, 5, 6)$, the mean is $\frac{15}{4}$, and the variance is $\frac{1}{4} ({(1 - \frac{15}{4})}^2 + {(3 - \frac{15}{4})}^2 + {(5 - \frac{15}{4})}^2 + {(6 - \frac{15}{4})}^2) = \frac{59}{16}$. **Constraints** | Test Point ID | $n \le$ | $a_i \le$ | |:-:|:-:|:-:| | $1 \sim 3$ | $4$ | $10$ | | $4 \sim 5$ | $10$ | $40$ | | $6 \sim 8$ | $15$ | $20$ | | $9 \sim 12$ | $20$ | $300$ | | $13 \sim 15$ | $50$ | $70$ | | $16 \sim 18$ | $100$ | $40$ | | $19 \sim 22$ | $400$ | $600$ | | $23 \sim 25$ | ${10}^4$ | $50$ | For all testdata, it is guaranteed that $1 \le n \le {10}^4$ and $1 \le a_i \le 600$. Translated by ChatGPT 5