題干：

Once at a team training Vasya, Petya and Sasha got a problem on implementing linear search in an array.

According to the boys, linear search works as follows. The array elements in a pre-selected order are in turn compared with the number that you need to find. Once you find the array element that is equal to the required one, the search ends. The efficiency of the algorithm is the number of performed comparisons. The fewer comparisons the linear search has made, the more effective it is.

Vasya believes that a linear search would work better if it sequentially iterates through the elements, starting with the?1-st one (in this problem we consider the elements of the array indexed from?1?to?n) and ending with the?n-th one. And Petya says that Vasya is wrong: the search will need less comparisons if it sequentially iterates the elements starting from the?n-th and ending with the?1-st one. Sasha argues that the two approaches are equivalent.

To finally begin the task, the teammates decided to settle the debate and compare the two approaches on an example. For this, they took an array that is a permutation of integers from?1?to?n, and generated?m?queries of the form: find element with value?bi?in the array. They want to calculate for both approaches how many comparisons in total the linear search will need to respond to all queries. If the first search needs fewer comparisons, then the winner of the dispute is Vasya. If the second one does, then the winner is Petya. If both approaches make the same number of comparisons, then Sasha's got the upper hand.

But the problem is, linear search is too slow. That's why the boys aren't going to find out who is right before the end of the training, unless you come in here. Help them to determine who will win the dispute.

Input

The first line contains integer?n?(1?≤?n?≤?105)?— the number of elements in the array. The second line contains?n?distinct space-separated integers?a1,?a2,?...,?an?(1?≤?ai?≤?n)?— the elements of array.

The third line contains integer?m?(1?≤?m?≤?105)?— the number of queries. The last line contains?m?space-separated integers?b1,?b2,?...,?bm?(1?≤?bi?≤?n)?— the search queries. Note that the queries can repeat.

Output

Print two integers, showing how many comparisons Vasya's approach needs and how many comparisons Petya's approach needs. Separate the numbers by spaces.

Please, do not use the?%lld?specifier to read or write 64-bit integers in С++. It is preferred to use?cin,?cout?streams or the?%I64d?specifier.

Examples

Input

2 1 2 1 1

Output

1 2

Input

2 2 1 1 1

Output

2 1

Input

3 3 1 2 3 1 2 3

Output

6 6

Note

In the first sample Vasya's approach will make one comparison (it starts with the?1-st element and immediately finds the required number), and Petya's approach makes two comparisons (first he compares with the?2-nd array element, doesn't find the search item and compares with the?1-st element).

In the second sample, on the contrary, Vasya's approach will need two comparisons (first with?1-st element, and then with the?2-nd), and Petya's approach will find the required value in one comparison (the first comparison with the?2-nd element).

題目大意：

? ?就是告訴你一組數(shù)，，m個(gè)詢問值為x的數(shù)字的位置。第一個(gè)人從左邊數(shù)，第二個(gè)人從右邊數(shù)，數(shù)到這個(gè)數(shù)就停止。問你每個(gè)人在m個(gè)詢問中共需要數(shù)多少個(gè)數(shù)、

解題報(bào)告：

? ?兩種解法，，第一種權(quán)值數(shù)組復(fù)雜度o(n+m)、、第二種STL復(fù)雜度o((n+m)logn)、、看代碼吧不難。。

AC代碼1：（124ms）

#include<cstdio> #include<iostream> #include<algorithm> #include<queue> #include<map> #include<vector> #include<set> #include<string> #include<cmath> #include<cstring> #define ll long long #define pb push_back #define pm make_pair #define fi first #define se second using namespace std; const int MAX = 2e5 + 5; ll id[MAX]; int n,m; int main() {cin>>n;ll tmp;for(int i=0; i<n; i++) {scanf("%lld",&tmp);id[tmp]=i;}ll ans1=0,ans2=0;cin>>m;while(m--) {scanf("%d",&tmp);tmp=id[tmp];ans1+=tmp;ans2+=n-tmp;}printf("%lld %lld\n",ans1,ans2);return 0 ; }

AC代碼2：（374ms）

#include<cstdio> #include<iostream> #include<algorithm> #include<queue> #include<map> #include<vector> #include<set> #include<string> #include<cmath> #include<cstring> #define ll long long #define pb push_back #define pm make_pair #define fi first #define se second using namespace std; const int MAX = 2e5 + 5; multiset<pair<ll,int> > s1,s2; multiset<pair<ll,int> > :: iterator it; ll a[MAX],b[MAX]; int main() {ll n,m,tmp;ll ans1=0,ans2=0;cin>>n;for(int i = 1; i<=n; i++) {scanf("%lld",a+i);s1.insert(pm(a[i],i));}reverse(a+1,a+n+1);for(int i = 1; i<=n; i++) {s2.insert(pm(a[i],i));}cin>>m;while(m--) {scanf("%lld",&tmp);it = s1.lower_bound(pm(tmp,0)); // printf("%lld %d\n",(*it).fi,(*it).second);ans1 += s1.lower_bound(pm(tmp,0))->second;ans2 += s2.lower_bound(pm(tmp,0))->second;}printf("%lld %lld\n",ans1,ans2);return 0 ;}

?

總結(jié)

以上是生活随笔為你收集整理的【CodeForces - 227B 】Effective Approach （STL，思维）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。