8891: NOIP2021 T3：方差（variance）
[Creator : ]
Description
给定长度为 $n$ 的非严格递增正整数数列 $1 \le a_1 \le a_2 \le \cdots \le a_n$。每次可以进行的操作是：任意选择一个正整数 $1 < i < n$，将 $a_i$ 变为 $a_{i - 1} + a_{i + 1} - a_i$。求在若干次操作之后，该数列的方差最小值是多少。请输出最小值乘以 $n^2$ 的结果。
其中方差的定义为：数列中每个数与平均值的差的平方的平均值。更形式化地说，方差的定义为 $D = \frac{1}{n} \sum_{i = 1}^{n} {(a_i - \bar a)}^2$，其中 $\bar a = \frac{1}{n} \sum_{i = 1}^{n} a_i$。
其中方差的定义为：数列中每个数与平均值的差的平方的平均值。更形式化地说，方差的定义为 $D = \frac{1}{n} \sum_{i = 1}^{n} {(a_i - \bar a)}^2$，其中 $\bar a = \frac{1}{n} \sum_{i = 1}^{n} a_i$。
Input
输入的第一行包含一个正整数 $n$，保证 $n \le {10}^4$。
输入的第二行有 $n$ 个正整数，其中第 $i$ 个数字表示 $a_i$ 的值。数据保证 $1 \le a_1 \le a_2 \le \cdots \le a_n$。
输入的第二行有 $n$ 个正整数，其中第 $i$ 个数字表示 $a_i$ 的值。数据保证 $1 \le a_1 \le a_2 \le \cdots \le a_n$。
Output
输出仅一行，包含一个非负整数，表示你所求的方差的最小值的 $n^2$ 倍。
Constraints
| 测试点编号 | $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$ |
对于所有的数据，保证 $1 \le n \le {10}^4$，$1 \le a_i \le 600$。
|:-:|:-:|:-:|
| $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$ |
对于所有的数据，保证 $1 \le n \le {10}^4$，$1 \le a_i \le 600$。
Sample 1 Input
4
1 2 4 6
Sample 1 Output
52
对于 $(a_1, a_2, a_3, a_4) = (1, 2, 4, 6)$，第一次操作得到的数列有 $(1, 3, 4, 6)$，第二次操作得到的新的数列有 $(1, 3, 5, 6)$。之后无法得到新的数列。
对于 $(a_1, a_2, a_3, a_4) = (1, 2, 4, 6)$，平均值为 $\frac{13}{4}$，方差为 $\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}$。
对于 $(a_1, a_2, a_3, a_4) = (1, 3, 4, 6)$，平均值为 $\frac{7}{2}$，方差为 $\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}$。
对于 $(a_1, a_2, a_3, a_4) = (1, 3, 5, 6)$，平均值为 $\frac{15}{4}$，方差为 $\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}$。
对于 $(a_1, a_2, a_3, a_4) = (1, 2, 4, 6)$，平均值为 $\frac{13}{4}$，方差为 $\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}$。
对于 $(a_1, a_2, a_3, a_4) = (1, 3, 4, 6)$，平均值为 $\frac{7}{2}$，方差为 $\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}$。
对于 $(a_1, a_2, a_3, a_4) = (1, 3, 5, 6)$，平均值为 $\frac{15}{4}$，方差为 $\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}$。
Sample 2 Input
10
6 19 34 35 56 63 82 82 83 99
Sample 2 Output
59865
Sample 3 Input
50
1 6 25 27 27 28 29 30 32 32 32 32 32 32 32 32 32 32 32 34 36 38 39 40 40 42 45 49 50 51 52 53 53 54 54 54 56 57 57 57 59 59 59 59 61 63 63 63 64 66
Sample 3 Output
252100
400
1 1 2 2 3 3 4 4 4 4 4 5 6 6 7 7 8 9 9 9 9 11 12 13 13 13 13 13 13 13 14 14 14 14 14 15 15 16 17 18 19 19 20 20 20 21 21 21 21 21 23 24 25 25 26 26 26 26 26 27 28 28 29 29 29 29 29 29 30 30 31 31 31 31 31 31 32 32 32 32 33 34 34 35 36 43 44 45 46 47 48 49 54 55 55 56 114 356 356 356 357 357 358 359 359 359 360 361 362 362 363 363 363 364 364 364 365 366 366 366 367 367 367 368 369 369 370 370 371 372 373 376 377 377 378 379 380 380 380 380 380 381 381 382 383 383 383 383 384 385 386 386 387 388 388 389 389 390 390 390 390 390 390 391 392 399 399 399 400 401 411 412 413 413 413 413 413 413 414 414 414 414 414 414 414 414 415 416 417 418 418 418 418 419 420 420 424 425 425 426 427 427 428 429 429 429 429 429 429 429 429 429 430 431 432 433 434 434 434 434 435 435 436 436 437 437 437 437 437 437 437 437 438 438 439 439 440 440 441 441 441 442 442 443 444 444 444 447 448 448 449 449 457 457 458 459 460 460 461 462 463 463 463 464 464 464 464 465 465 465 465 466 466 467 468 468 468 469 470 470 471 471 471 471 471 471 471 471 472 472 472 472 473 474 475 476 477 478 478 479 480 481 481 481 482 482 482 482 482 483 484 484 484 484 484 484 484 485 485 485 485 485 486 487 487 487 488 489 489 489 489 490 491 491 492 493 494 494 494 495 495 495 495 496 496 496 496 496 496 497 497 497 498 498 498 499 500 500 500 501 502 502 502 503 504 504 504 507 507 507 508 510 510 510 512 513 513 513 513 514 515 515 515 516 516 517 518 518 518 518 518 518 519 520 534 553 576 580 592 600
305460375
HINT
相同题目：洛谷 P7962。