『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<0)
{
putchar('-');
x=-x;
}
if(x<10)
{
putchar(x+48);
return;
}
print(x/10);
putchar(x%10+48);
}
```
输入输出格式
输入格式
第一行，一个整数，表示 $n$。
第二行，$n$ 个整数，表示 $a_1,a_2,\dots,a_n$。
第三行，$n$ 个整数，表示 $b_1,b_2,\dots,b_n$。
输出格式
共一行，一个整数，表示答案。
输入输出样例
输入样例 #1
2
1 10
1 10输出样例 #1
81输入样例 #2
3
1 2 3
3 4 5输出样例 #2
26说明
对于 $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)$。