P8920 "MdOI R5" Variance

Subtasks 1 to 5 use the original testdata, and Subtask 6 uses hack testdata.

Given two integer sequences $a, b$ of length $n$, satisfying: - $\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$. There is a real-valued sequence $c$ of length $n$ such that $c_i \in [a_i, b_i]$. Find the maximum possible variance of $c$. You only need to output the result after multiplying the answer by $n^2$. It is easy to prove that this is an integer.

The first line contains one integer $n$. The second line contains $n$ integers $a_1, a_2, \dots, a_n$. The third line contains $n$ integers $b_1, b_2, \dots, b_n$.

One line containing one integer, which is the answer.

The variance of a sequence $a$ of length $n$ is $\dfrac{1}{n}\sum\limits_{i=1}^n (a_i-\overline{a})^2$, where $\overline{a}=\dfrac{1}{n}\sum\limits_{i=1}^n a_i$. During the computation for this problem, numbers exceeding the range of `long long` may appear. In that case, you may need to use `__int128`. We provide the following code, which can be used to output a value of type `__int128`: ``` cpp void print(__int128 x) { if(x