Problem Background

NOIP2013 Senior Group D1T2

Problem Description

Hanhan has two boxes of matches, each containing $n$ matches. Each match has a height. Now, the matches in each box are arranged in a line, with the heights of the matches in the same line being distinct. The distance between the two lines of matches is defined as: $\sum (a_i-b_i)^2$.

Where $a_i$ represents the height of the $i$-th match in the first line, and $b_i$ represents the height of the $i$-th match in the second line.

Adjacent matches in each line can be swapped. You are asked to swap the matches to minimize the distance between the two lines. What is the minimum number of swaps needed to achieve this minimum distance? If the number is too large, output the result of the minimum number of swaps modulo $10^8-3$.

Input Format

There are three lines in total. The first line contains an integer $n$, indicating the number of matches in each box.

The second line contains $n$ integers, separated by spaces, representing the heights of the matches in the first line.

The third line contains $n$ integers, separated by spaces, representing the heights of the matches in the second line.

Output Format

An integer representing the result of the minimum number of swaps modulo $10^8-3$.

Sample Input and Output

Sample Input #1

4
2 3 1 4
3 2 1 4

Sample Output #1

1

Sample Input #2

4
1 3 4 2
1 7 2 4

Sample Output #2

2

Notes

Explanation of Sample Input and Output #1

The minimum distance is $0$, and the minimum number of swaps needed is $1$. For example, swap the first two matches in the first line or the first two matches in the second line.

Explanation of Sample Input and Output #2

The minimum distance is $10$, and the minimum number of swaps needed is $2$. For example, swap the middle two matches in the first line, and then swap the last two matches in the second line.

Data Range

For $10\%$ of the data, $1 \leq n \leq 10$;

For $30\%$ of the data, $1 \leq n \leq 100$;

For $60\%$ of the data, $1 \leq n \leq 10^3$;

For $100\%$ of the data, $1 \leq n \leq 10^5$, $0 \leq$ match height $< 2^{31}$.

见题面 Input 部分

见题面 Output 部分