『MdOI R5』Variance

给定两个长度为 $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); } ``` ## Input 第一行，一个整数，表示 $n$。 第二行，$n$ 个整数，表示 $a_1,a_2,\dots,a_n$。 第三行，$n$ 个整数，表示 $b_1,b_2,\dots,b_n$。 ## Output 共一行，一个整数，表示答案。 [samples] ## Background Subtask 1~5 为原数据，Subtask 6 为 hack 数据。 ## Note 对于 $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)$。