P8920 『MdOI R5』Variance
题目背景
Subtask 1~5 为原数据，Subtask 6 为 hack 数据。
题目描述
给定两个长度为 $n$ 的整数序列 $a,b$，满足：
- $\forall i\in [1,n),a_i\le a_{i+1},b_i\le b_{i+1}$。
- $\forall i\in [1,n],a_i\le b_i$。
有一个长度为 $n$ 的实数序列 $c$，满足 $c_i\in [a_i,b_i]$，求 $c$ 的方差的最大值。
你只需要输出答案乘上 $n^2$ 之后的结果。容易证明这是一个整数。
### 提示
一个长度为 $n$ 的序列 $a$ 的方差为：$\dfrac{1}{n}\sum\limits_{i=1}^n (a_i-\overline{a})^2$。其中 $\overline{a}=\dfrac{1}{n}\sum\limits_{i=1}^n a_i$。
本题的计算过程中可能会涉及到超过 `long long` 范围的数，此时可能需要用到 `__int128` 进行处理。
我们提供了以下代码，它可以用于输出一个 `__int128` 类型的数：
``` cpp
void print(__int128 x)
{
if(x
输入格式
无
输出格式
无
说明/提示
对于 $100\%$ 的数据，$1\le n\le 10^6$，$1\le a_i,b_i\le 10^9$。
$\operatorname{Subtask} 1(10\%)$：$n\le 2\times 10^3$，$a_i=b_i\le 10^5$。
$\operatorname{Subtask} 2(20\%)$：$n\le 10$，$a_i,b_i\le 5$。
$\operatorname{Subtask} 3(20\%)$：$n\le 2\times 10^3$，$a_i,b_i\le 10^5$。
$\operatorname{Subtask} 4(20\%)$：$n\le 10^5$，$a_i,b_i\le 2\times 10^3$。
$\operatorname{Subtask} 5(30\%)$：无特殊限制。
#### 样例说明 1
$c$ 只可能为 $(1,10)$。
#### 样例说明 2
一种最优的 $c$ 为 $(1,2,5)$。