Queuing Up

Problem Description

On an ancient planet, a group of people gather every year for a grand anniversary celebration. Before entering the venue, everyone lines up into two teams at the entrance, each team having exactly $n$ people. In the first team the $i$-th person has height $a_i$, and in the second team the $i$-th person has height $b_i$.

While queuing, people like to chat amiably with the partner standing at the same position in the other team. However, if the two people differ too much in height, they feel a bit awkward. The awkwardness index $g_i$ of the two is related to their height difference by $g_i = (a_i - b_i)^2$.

To minimize the awkwardness as much as possible, people in each team may swap positions with an adjacent neighbor any number of times, but only within their own team. What is the minimum number of swaps needed so that the total awkwardness $\sum (a_i - b_i)^2$ is minimized? If the answer is too large, output this minimum number of swaps modulo $10^8 - 7$.

It is guaranteed that within each team all heights are pairwise distinct.

Input Format

The input consists of three lines. The first line is a positive integer $n$, the number of people in each team. The second line contains $n$ integers separated by spaces, the heights of the first team. The third line contains $n$ integers separated by spaces, the heights of the second team.

Output Format

Output one integer: the minimum number of swaps.

Sample Input

4
2 3 1 4
3 2 1 4

Sample Output

1

Sample Explanation

We only need to swap the first two people of the first team, or swap the first two people of the second team. Then everyone chats with a partner of exactly the same height, making the total awkwardness $0$, which is minimal.

Constraints

$1 \leq n \leq 10^5$, $0 \leq a_i, b_i < 2^{31}$; it is guaranteed that within each team all heights are pairwise distinct.