古老的星球上有这样一群人，他们每年都会参加盛大的周年庆。在进入场地之前所有人在入口排成两队，每队人数都是 $n$ 人，第一队第 $i$ 人身高为 $a_i$，第二队第 $i$ 人身高为 $b_i$。

人们在排队时，喜欢跟另一队相同位置的伙伴亲切地交谈。但是如果这两人身高相差太多，他们会感到有些尴尬，两人的尴尬指数 $g_i$ 与身高差呈这样一种关系：$g_i=(a_i-b_i{)}^2$。

为了尽可能减轻尴尬，每队的人都可以与前后相邻者交换位置，次数不限，但只能在同队范围内交换。问最少需要交换多少次位置，可以使得总体尴尬度 $\sum (a_i-b_i{)}^2$ 最小。如果答案太大，请输出这个最少交换次数对 $10^8-7$ 取模的结果。

保证每队人的身高两两不同。

输入格式

输入共三行。第一行是一个正整数 $n$，表示每队的人数。 第二行有 $n$ 个整数，每两个整数用一个空格隔开，表示第一队人们的身高。 第三行有 $n$ 个整数，每两个整数用一个空格隔开，表示第二队人们的身高。

输出格式

一个整数，表示最少的交换次数。

数据范围

$1\le n\le 10^5,0\le a_i,b_i<2^{31}$，保证每队人们的身高各不相同

输入样例

4
2 3 1 4
3 2 1 4

输出样例

1

样例解释

只需交换第一队前两人，或者交换第二队前两人。这样人们都跟与自己身高相同的伙伴交谈，总体尴尬度为$0$，即最小。

解题思路

题意规定尴尬指数的计算公式为$g_i=(a_i-b_i{)}^2$，而我们可以看出${\sum }_{i=1}^n{g}_i$的和中$\sum a_i^2+b_i^2$这部分是保持不变的，所以要使尴尬指数最小，只需要使$\sum a_i\ast b_i$最小。

根据公式$(a_i+b_i{)}^2\ge 2\ast a_i\ast b_i(a_i=b_i$时等式成立$)$可以看出，我们只需要使得任意两个人的身高尽可能的接近就可以了。

直观来讲，就是当两个队列都是单调递增的时候，尴尬指数最小。但是题目要求交换次数最小，那么我们就需要把一个队列的顺序转化为另外一个队列的顺序。

求最小相邻交换次数，就是求逆序数。

这里简单介绍一下逆序数：

对于序列$15234$，指定标准为升序排序（也可以为降序）。那么$1$的的逆序数就是在它的前面，比它大的数（不符合升序），这里显然是$0$；通过计算，$5,2,3,4$的逆序数分别为$0,1,1,1$，那么整个序列的逆序数为$3$（累加）。

显然两个队列都是没有顺序的。但是没关系，我们不需要值有顺序，只需要索引有顺序就可以了。

我们将一个元素的值转换为它需要对应元素的索引，这样就可以计算逆序数了（将转换后的序列重新变为升序排序）。

计算逆序数的方法通常是归并排序（这里不做介绍，只是简单给出实现）。

最后，AC代码如下：

#include <iostream>
#include <algorithm>
using namespace std;
const int max_n = 1e5;
const long long mod_num = 1e8 - 7;

struct node { int idx, val; } a[max_n], b[max_n];
long long ans = 0;
int temp[max_n];

void merge_sort(node arr[], int l, int r) {
	if (l == r) return;

	int m = l + r >> 1;
	merge_sort(arr, l, m);
	merge_sort(arr, m + 1, r);

	long long i = l, j = m + 1, k = l;
	while (i <= m && j <= r) {
		if (arr[i].val > arr[j].val) {
			temp[k] = arr[j].val;
			j++, k++;
			ans = (ans + m - i + 1LL) % mod_num;//累计逆序数
		}
		else {
			temp[k] = arr[i].val;
			i++, k++;
		}
	}

	while (i <= m) temp[k++] = arr[i++].val;
	while (j <= r) temp[k++] = arr[j++].val;
	for (i = l; i <= r; i++) arr[i].val = temp[i];
}

int main() {
	int n;
	cin >> n;
	for (int i = 0; i < n; i++) {
		//scanf("%d", a + i);
		cin >> a[i].val;
		a[i].idx = i;
	}
	for (int i = 0; i < n; i++) {
		//scanf("%d", b + i);
		cin >> b[i].val;
		b[i].idx = i;
	}

	sort(a, a + n, [](node n1, node n2) {
		return n1.val < n2.val;
		});
	sort(b, b + n, [](node n1, node n2) {
		return n1.val < n2.val;
		});

	for (int i = 0; i < n; i++) {
		a[i].val = b[i].idx;
	}
	sort(a, a + n, [](node n1, node n2) {
		return n1.idx < n2.idx;
		});

	merge_sort(a, 0, n - 1);
	cout << ans << endl;
	return 0;
}