Dog Trick Competition 2

Task

RANDy is back at it again, but now he is entering a more advanced dog trick competition with his canine friend, Pompieru.

There are $K$ tricks which can be performed in this competition, numbered from $1$ to $K$ and Pompieru knows how to perform all of them.
However, performing specific tricks one after the other is not always possible: he can only perform trick $b$ right after trick $a$ if he has been trained to do so.
RANDy trained Pompieru to perform $M$ pairs of consecutive tricks $(A_i, B_i)$, meaning that Pompieru knows how to perform trick $B_i$ right after trick $A_i$.

The participants are required to perform $N$ tricks $T_0, T_1, \ldots, T_{N-1}$ in this specific order.
Pompieru will first perform the trick $T_0$ earning $2$ points. When Pompieru finishes performing the trick $T_i$ he will move on to trick $T_{i + 1}$.
If he can perform the trick $T_{i + 1}$ right after $T_i$ he will earn $2$ points, otherwise he can choose to perform some (one or more) in between tricks, enabling him to perform $T_{i + 1}$. If he succeeds this way, he will earn $1$ point.
If not, he will be disqualified from the contest, earning as many points as he gathered prior to his disqualification.

Help RANDy and Pompieru find the number of points $P$ they can score in this competition.

Input data

The input file consists of:

• a line containing integers $N$ and $K$.
• a line containing the $N$ integers $T_{0}, \, \ldots, \, T_{N-1}$.
• a line containing integer $M$.
• $M$ lines, the $i$-th of which consisting of integers $A_{i}$, $B_{i}$.

Output data

The output file must contain a single line consisting of integer $P$.

Constraints and clarifications

• $2 \le N \le 250 \ 000$.
• $1 \le K \le 250 \ 000$.
• $1 \le M \le 250 \ 000$.
• $1 \le T_i \le K$ for each $i = 0 \ldots N - 1$.
• $T_i \neq T_{i + 1}$ for each $i = 0 \ldots N - 2$.
• $1 \le A_i, B_i \le K$ and $A_i \neq B_i$ for each $i = 0 \ldots M - 1$.
• All the ordered pairs $(A_i, B_i)$ are distinct.
• It is allowed to perform a trick multiple times.

Example 1

stdin

4 5
1 3 2 5
5
1 3
3 4
4 2
2 3
4 5

stdout

6

Explanation

In the first sample case, Pompieru earns $2$ points for performing the first trick. He then earns $2$ more points because he can perform trick $3$ right after trick $1$,
then earns one more point performing trick $4$ and then trick $2$. After that he earns one more point by performing tricks $3$, $4$, and finally $5$.

Example 2

stdin

4 5
1 3 5 2
5
1 3
3 4
4 2
2 3
4 5

stdout

5

Explanation

In the second sample case, Pompieru earns $2$ points for performing the first trick. He then earns $2$ more points because he can perform trick $3$ right after trick $1$,
then earns one more point performing trick $4$ and then trick $5$. After that, there is no sequence of tricks he can do in order to perform trick $2$, so he gets disqualified, earning a total of $5$ points.