It's almost Christmas time, and you realize you need to start getting presents for your $M$ relatives! The $i$th of your relatives has asked you for a handknit multicoloured scarf, where the first foot is of colour $a_i$ and the last foot is $b_i$.

Lucky for you, you just happen to have an $N$ foot, multicoloured scarf lying around where $i$th foot is composed of a single colour $c_i$. You decide that sending just 1 relative a gift is enough, and that surely they won't notice that you just trimmed off parts of the scarf and sent it to them…right?

Maybe you should make it as long as possible so they don't notice…

Constraints

Subtask 1 [10%]

$1\le N\le 1000$
$1\le M\le 1000$
$1\le a_i,b_i,c_i\le {10}^6$

Subtask 2 [10%]

$1\le N\le {10}^5$
$M=1$
$1\le a_i,b_i,c_i\le {10}^6$

Subtask 3 [80%]

$1\le N\le {10}^5$
$1\le M\le {10}^5$
$1\le a_i,b_i,c_i\le {10}^6$

Input Specification

The first line of input contains two space-separated integers, $N$ and $M$, the length of the scarf, and the number of relatives.
The second line of input contains $N$ space-separated integers $c_i$, where the $i$th integer is the colour of the $i$th foot of the scarf.
The next $M$ lines each contain two space-separated integers, $a_i$ and $b_i$, the colour of the first and last foot of the scarf your $i$th relative wants.

Output Specification

Output a single integer $L$, the longest possible contiguous scarf that can be obtained by trimming off the ends, such that the colours of the first and last foot correspond to one of your relative's requests.

Sample Input 1

4 2
1 2 3 4
1 3
2 3

Sample Output 1

3

Sample Input 2

3 2
1 2 3
2 5
1 1

Sample Output 2

1

Sample Input 3

3 1
1 2 3
3 2

Sample Output 3

0