Lotto Losers
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 -indexed position where it first occurs in the winning array, or
if it isn't a winning ticket. The brothers' total score is the sum of all their ticket prizes. Each ticket additionally costs
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 , representing how many winning numbers there are. The next line contains
space-separated integers
detailing each of the winning ticket numbers. They are given in random order and may contain duplicates.
The following line contains an integer , representing how many tickets the brothers bought. The following line
space-separated integers
, with each one representing the ticket number of the
th ticket bought.
Output
Output the total profits of the brothers, that is, the sum of their ticket scores (the -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
cost for each ticket.
Your solution must run in linear expected time — — 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 dollars. Of these tickets,
has a score of
as that is where it first occurs in the array.
has a score of
, and
has a score of
as it isn't a winning ticket. Thus,
is the final result, indicating that the brothers lost money in this case.
Comments