Background

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

Problem Description

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.

Input Format

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$.

Output Format

One line containing one integer, which is the answer.

2
1 10
1 10

81

3
1 2 3
3 4 5

26

Hint

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:

void print(__int128 x)
{
	if(x<0)
	{
		putchar('-');
		x=-x;
	}
	if(x<10)
	{
		putchar(x+48);
		return;
	}
	print(x/10);
	putchar(x%10+48);
}

Constraints: for $100\%$ of the data, $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\%)$: no special constraints.

Sample Explanation 1

$c$ can only be $(1,10)$.

Sample Explanation 2

One optimal $c$ is $(1,2,5)$.

Translated by ChatGPT 5