Maximizing Scaled Variance in Bounded Sequences

You are given two integer sequences \(a\) and \(b\) of length \(n\) satisfying the following conditions:

• \(a_1 \le a_2 \le \cdots \le a_n\) and \(b_1 \le b_2 \le \cdots \le b_n\).
• For all \(1 \le i \le n\), \(a_i \le b_i\).

There is also a sequence \(c\) of \(n\) real numbers where for all \(1 \le i \le n\), \(c_i \in [a_i, b_i]\). Your task is to choose \(c\) so that the variance of \(c\) is maximized. Recall that the variance of a sequence \(x\) of length \(n\) is defined as \[ \text{Var}(x)=\frac{1}{n}\sum_{i=1}^n (x_i-\overline{x})^2, \quad \text{with } \overline{x}=\frac{1}{n}\sum_{i=1}^n x_i. \] You only need to output the final answer multiplied by \(n^2\). It can be shown that the answer is always an integer.

Hint: In the process of calculating the answer, the numbers involved might exceed the range of long long. Therefore, in some languages (such as C++), you may need to use __int128 to handle large integers. The following C++ function is provided to print a value of type __int128:

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

inputFormat

The input consists of three lines:

1. An integer \(n\) representing the length of the sequences.
2. \(n\) space-separated integers representing the sequence \(a\): \(a_1, a_2, \ldots, a_n\).
3. \(n\) space-separated integers representing the sequence \(b\): \(b_1, b_2, \ldots, b_n\).

It is guaranteed that \(a_1 \le a_2 \le \cdots \le a_n\), \(b_1 \le b_2 \le \cdots \le b_n\), and \(a_i \le b_i\) for each \(1 \le i \le n\).

outputFormat

Output a single integer: the maximum possible variance of the sequence \(c\) multiplied by \(n^2\). As shown in the hint, if \(c\) has variance \(\text{Var}(c) = \frac{1}{n}\sum_{i=1}^n(c_i-\overline{c})^2\), you should output \[ n\sum_{i=1}^n c_i^2 - \Bigl(\sum_{i=1}^n c_i\Bigr)^2, \] which is guaranteed to be an integer.

sample

1
5
10

0