Minimum Adjacent Swaps for Matchstick Alignment

Hannah has two boxes containing matchsticks. Each box contains ( n ) matchsticks, each with a unique height within that box. The matchsticks in each box are arranged in a column. The distance between the two columns is defined as ( \sum_{i=1}^{n} (a_i - b_i)^2 ), where ( a_i ) and ( b_i ) are the heights of the matchstick in the ( i^{th} ) position of the first and second columns respectively.

In each column, you are allowed to swap two adjacent matchsticks (each swap counts as one operation). By performing such swaps, rearrange both columns so that the distance between them is minimized. Determine the minimum total number of swaps required to achieve the minimum distance. Since this number might be large, output the result modulo (10^8-3) (i.e. modulo ( 10^8-3 )).

Hint: By the rearrangement inequality, the distance ( \sum (a_i - b_i)^2 ) is minimized when both columns are sorted in the same order (either increasing or decreasing). Note that the minimum number of adjacent swaps needed to sort an array is equal to its inversion count.

inputFormat

The first line contains an integer ( n ) (the number of matchsticks in each box).

The second line contains ( n ) space-separated integers representing the heights of the matchsticks in the first box.

The third line contains ( n ) space-separated integers representing the heights of the matchsticks in the second box.

outputFormat

Output a single integer: the minimum total number of adjacent swaps (performed in both columns) required to attain the optimal arrangement, modulo (10^8-3).

sample

2
2 1
1 2

1