## NOIP '21 P3 - Variance

View as PDF

Points: 20 (partial)
Time limit: 1.0s
Memory limit: 512M

Problem type

You are given a sequence of nondecreasing positive integers .

At each step, you can perform the following operation: Choose any positive integer , change to .

Determine the minimum variance of the sequence after performing any number of operations.

The variance is the average of the squared differences between numbers and their mean value. Formally, variance is where .

#### Input Specification

The first line contains a positive integer . It is guaranteed that .

The second line contains positive integers where the -th number represents the value of . The data guarantee that .

#### Output Specification

Output a single nonnegative integer representing times the minimum variance you determine.

#### Sample Input 1

4
1 2 4 6

#### Sample Output 1

52

#### Sample 1 Explanation

For , after the first operation, we can get . After the second operation, we can get . After that we cannot get any new sequence.

For , the mean is , the variance is .

For , the mean is , the variance is .

For , the mean is , the variance is .