#include<iostream> #include<algorithm> using namespace std; const int N(100005),M(99999997); struct node{ int data,no; bool operator <(const node &x)const { return data<x.data; } }; int a[N],b[N],c[N],tmp[N]; node t[N]; int merge(int low,int mid,int high) { int i,j,k,t(0); for (i=low,j=mid+1,k=low;i<=mid&&j<=high;) if (c[i]<c[j]) tmp[k++]=c[i++]; else tmp[k++]=c[j++],t=(t+mid+1-i)%M; while (i<=mid) tmp[k++]=c[i++]; while (j<=high)tmp[k++]=c[j++]; for (i=low;i<=high;i++) c[i]=tmp[i]; return t; } int solve(int low,int high) { if (low>=high) return 0; int mid,t(0); mid=(low+high)/2; t=(t+solve(low,mid))%M; t=(t+solve(mid+1,high))%M; t=(t+merge(low,mid,high)%M); return t; } int main() { //ifstream cin("match.in"); //ofstream cout("match.out"); int n; cin>>n; for (int i=1;i<=n;i++) { cin>>a[i]; t[i].data=a[i]; t[i].no=i; } sort(t+1,t+n+1); for (int i=1;i<=n;i++) a[i]=t[i].no; for (int i=1;i<=n;i++) { cin>>b[i]; t[i].data=b[i]; t[i].no=i; } sort(t+1,t+n+1); for (int i=1;i<=n;i++) b[t[i].no]=i; for (int i=1;i<=n;i++) c[i]=a[b[i]]; cout<<solve(1,n)<<endl; return 0; } /************************************************************** Problem: 2325 User: admin Language: C++ Result: Accepted Time:177 ms Memory:4420 kb ****************************************************************/