Tunnel

Interview

Time limit2sMemory limit512 MB

Summary

Given the entry order and exit order of N cars through a tunnel, count how many cars must have overtaken another car.

Level: Medium4 of 10
Topics: Array, Hash map, Greedy, Implementation
Solved: No attempts yet

Problem

Mirko stands at the entrance of a tunnel and Slavko stands at the exit. Each of them writes down the licence plate of every car in the order the cars drive past, and sends the list to a police patrol a few kilometres down the road.

From the two lists the patrol can decide without any doubt that certain drivers overtook inside the tunnel, which is strictly forbidden.

Write a program that counts the drivers who can be proven to have overtaken.

Assume the traffic inside the tunnel behaved normally, with no collisions and no cars stopping.

Input

The first line contains the number of cars $N$ ( $1 \le N \le 1000$ ).

The next $N$ lines contain the licence plates in the order the cars entered the tunnel, one plate per line.

The next $N$ lines contain the licence plates of the same cars in the order they left the tunnel, one plate per line.

A licence plate is 6 to 8 characters long and uses only the uppercase English letters A to Z and the digits 0 to 9. The $N$ plates are all different.

Output

Print the number of drivers the police can certainly punish for illegal overtaking.

Examples7

Example 1

Input

3
ZG100LK
OS1234K
ST999D
ZG100LK
ST999D
OS1234K

Expected output

Example 2

Input

5
ZG508OK
PU305A
RI604B
ZG206A
ZG232ZF
PU305A
ZG232ZF
ZG206A
ZG508OK
RI604B

Expected output

Example 3
Input
```
1
AB1234
AB1234
```
Expected output
```
0
```
Example 4
Input
```
2
AAAAAA
BBBBBB
AAAAAA
BBBBBB
```
Expected output
```
0
```
Example 5
Input
```
2
AAAAAA
BBBBBB
BBBBBB
AAAAAA
```
Expected output
```
1
```

Example 6

Input

6
CAR000
CAR001
CAR002
CAR003
CAR004
CAR005
CAR005
CAR004
CAR003
CAR002
CAR001
CAR000

Expected output

Example 7

Input

7
ZG000000
ZG000001
ZG000002
ZG000003
ZG000004
ZG000005
ZG000006
ZG000000
ZG000001
ZG000002
ZG000003
ZG000004
ZG000005
ZG000006

Expected output