题目背景

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 类型的数：

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

输出格式

共一行，一个整数，表示答案。

2
1 10
1 10

81

3
1 2 3
3 4 5

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)$。