Lotto Losers


Submit solution

Points: 1
Time limit: 1.0s
Memory limit: 256M

Author:
Problem type
Allowed languages
C++, Java, Python

The brothers Jeff and Joey are at it again with their lottery ticket 'investments'. This time, however, they are using a different lottery system in which the winning tickets are not provided in sorted order, so it'll be harder to check whether they won or not.

Similarly to before, each tickets value is the 1-indexed position where it first occurs in the winning array, or 0 if it isn't a winning ticket. The brothers' total score is the sum of all their ticket prizes. Each ticket additionally costs 5 dollars, so you should subtract the costs of all their tickets from their score to determine their profits.

Input

The first line contains an integer n\ (1 \leq n \leq 10^6), representing how many winning numbers there are. The next line contains n space-separated integers x_i\ (1 \leq x_i \leq 10^6) detailing each of the winning ticket numbers. They are given in random order and may contain duplicates.

The following line contains an integer m\ (1 \leq m \leq 10^5), representing how many tickets the brothers bought. The following line m space-separated integers y_i\ (1 \leq y_i \leq 10^6), with each one representing the ticket number of the ith ticket bought.

Output

Output the total profits of the brothers, that is, the sum of their ticket scores (the 1-indexed position of the first occurrence of each of their tickets in the winning array, or 0 if it doesn't occur in the winning array), minus the $5 cost for each ticket.

Your solution must run in linear expected time — O(n+m) — or faster.

Example

Input 1
6
15 3 10000 6 3 10
3
3 6 9
Output 1
-9
Explanation 1

The 3 tickets bought by the brothers cost 15 dollars. Of these tickets, 3 has a score of 2 as that is where it first occurs in the array. 6 has a score of 4, and 9 has a score of 0 as it isn't a winning ticket. Thus, 2+4-15=-9 is the final result, indicating that the brothers lost money in this case.


Comments

There are no comments at the moment.