Conflict of Interest
Description
Some time ago, the owner of the cat Benedict decided that her pet was lonely while she was at work. So, she got a kitten named Tybalt.
Every morning, Benedict's owner takes two packs of food and puts the contents of the packs into two bowls (one bowl for each pack). Benedict's owner likes order, so the food packs are arranged in some order, and she plans to give them to the cats in that order. In other words, packs $1$ and $2$ are planned to be used on day $1$, packs $3$ and $4$ are planned to be used on day $2$, and so on.
There are $n$ types of food in total; for simplicity, let's assume that the food types are numbered from $1$ to $n$.
Each cat has its own personal rating of the food. The cat's rating is a list of food types, starting with the one the cat likes the most and ending with the one the cat likes the least. In other words, the earlier a food type appears in the list, the more the cat likes that food type.
So, when the owner fills both bowls, each cat runs to the bowl that contains the food with a higher rating from that cat's perspective. Sometimes both cats run to the same bowl. However, when they finish eating the contents of that bowl, they move on to eat from the other bowl.
If the bowls have the same food, the cats, upon realizing this, will eat from different bowls.
The owner wants to minimize the number of days that both cats eat from the same bowl. However, she doesn't want to change the order of using the food packs too much. If she plans to give a certain food pack on day $k$, she can use that pack on day $k$, day $k-1$ or day $k+1$, but not earlier or later. On each day, exactly two food packs should be used.
Your task is to determine the minimum possible number of days that both cats eat from the same bowl based on the food ratings for each cat and the owner's planned order of giving out the food.
The first line contains two integers $n$ and $m$ ($1 \le n \le 2 \cdot 10^5$; $2 \le m \le 2 \cdot 10^5$; $m$ is even) — the number of types of food and the number of food packs, respectively.
The second line contains $n$ integers $b_1, b_2, \dots, b_n$ ($1 \le b_i \le n$) — the cat Benedict's food rating. All $b_i$ are distinct.
The third line contains $n$ integers $t_1, t_2, \ldots, t_n$ ($1 \le t_j \le n$) — the kitten Tybalt's food rating. All $t_j$ are distinct.
The fourth line contains $m$ integers $a_1, a_2, \ldots, a_m$ ($1 \le a_p \le n$) — the initial order of food packs.
Output a single integer — the minimum possible number of days that both cats eat from the same bowl.
Input
The first line contains two integers $n$ and $m$ ($1 \le n \le 2 \cdot 10^5$; $2 \le m \le 2 \cdot 10^5$; $m$ is even) — the number of types of food and the number of food packs, respectively.
The second line contains $n$ integers $b_1, b_2, \dots, b_n$ ($1 \le b_i \le n$) — the cat Benedict's food rating. All $b_i$ are distinct.
The third line contains $n$ integers $t_1, t_2, \ldots, t_n$ ($1 \le t_j \le n$) — the kitten Tybalt's food rating. All $t_j$ are distinct.
The fourth line contains $m$ integers $a_1, a_2, \ldots, a_m$ ($1 \le a_p \le n$) — the initial order of food packs.
Output
Output a single integer — the minimum possible number of days that both cats eat from the same bowl.
5 14
4 3 1 2 5
5 3 1 4 2
4 3 4 4 2 1 5 3 5 5 3 2 1 4
5 12
3 5 4 1 2
2 3 4 5 1
3 5 4 1 5 1 3 4 3 1 5 3
4 12
3 4 1 2
2 3 4 1
3 1 4 3 3 1 2 2 3 2 4 1
5 14
3 5 4 1 2
2 3 4 5 1
3 5 4 1 5 1 3 4 3 1 5 3 2 4
0
2
0
1