Competition

Interview

Time limit1sMemory limit256 MB

Summary

Find the fewest seat changes that let Alice and Bob solve every solvable problem in contest order.

Level: Medium4 of 10
Topics: Greedy, Sorting
Solved: No attempts yet

Problem

Bob and Alice enter a programming contest as a team.

The contest has $N$ problems, and the two go through them in order from problem 1 to problem $N$ . A problem that neither of them can solve is skipped. Some problems only Alice can solve, and some only Bob can solve.

Whoever is sitting at the computer solves the problem. The two want to solve every problem they are able to solve while changing who sits at the computer as few times as possible. Either person can start at the computer.

Given the number of problems and the problems each of them can solve, find the minimum number of changes.

Input

The first line contains three integers $N$ , $A$ , and $B$ ( $1 \le N \le 10^9$ , $1 \le A \le \min(N, 5 \times 10^4)$ , $1 \le B \le \min(N, 5 \times 10^4)$ ).

The second line contains the $A$ problem numbers Alice can solve. The third line contains the $B$ problem numbers Bob can solve. Within one line the numbers are distinct and lie between 1 and $N$ , and they are not necessarily sorted.

Output

Print the minimum number of changes at the computer.

Examples8

Example 1
Input
```
5 2 3
2 4
1 5 3
```
Expected output
```
4
```
Example 2
Input
```
4 3 3
1 2 3
2 3 4
```
Expected output
```
1
```
Example 3
Input
```
4 3 3
1 3 4
4 3 1
```
Expected output
```
0
```
Example 4
Input
```
1 1 1
1
1
```
Expected output
```
0
```
Example 5
Input
```
2 1 1
1
2
```
Expected output
```
1
```
Example 6
Input
```
1000000000 1 1
1000000000
1
```
Expected output
```
1
```
Example 7
Input
```
3 2 2
1 3
2 3
```
Expected output
```
1
```
Example 8
Input
```
10 5 5
1 3 5 7 9
2 4 6 8 10
```
Expected output
```
9
```