题目描述

服装室里有两排待整理的校服编号牌，每排各有 $n$ 张。每张编号牌上写着一个尺码数，同一排内的尺码数互不相同。

若两排编号牌按当前位置一一对应，第 $i$ 个位置的两张编号牌尺码分别为 $a_i$ 和 $b_i$，则整理误差定义为

你可以在任意一排中反复交换相邻的两张编号牌。请在让整理误差达到最小的前提下，求最少需要进行多少次相邻交换。答案可能很大，请输出它对 $10^8-3$ 取模后的结果。

输入格式

输入共三行。

第一行一个整数 $n$，表示每排编号牌数量。

第二行包含 $n$ 个整数，表示第一排编号牌的尺码数。

第三行包含 $n$ 个整数，表示第二排编号牌的尺码数。

输出格式

输出一行一个整数，表示最少相邻交换次数对 $10^8-3$ 取模后的结果。

4
2 3 1 4
3 2 1 4

1

4
1 3 4 2
1 7 2 4

2

样例说明

第一组样例中，最小整理误差可以达到 $0$，只需交换其中一排的前两张编号牌。

第二组样例中，最小整理误差为 $10$，达到该误差至少需要 $2$ 次相邻交换。

数据范围

对于 $10\%$ 的数据，$1\le n\le 10$；

对于 $30\%$ 的数据，$1\le n\le 100$；

对于 $60\%$ 的数据，$1\le n\le 10^3$；

对于 $100\%$ 的数据，$1\le n\le 10^5$，$0\le$ 尺码数 $<2^{31}$。