It's almost Christmas time, and you realize you need to start getting presents for your relatives! The th of your relatives has asked you for a handknit multicoloured scarf, where the first foot is of colour and the last foot is .
Lucky for you, you just happen to have an foot, multicoloured scarf lying around where th foot is composed of a single colour . 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…
Subtask 1 [10%]
Subtask 2 [10%]
Subtask 3 [80%]
The first line of input contains two space-separated integers, and , the length of the scarf, and the number of relatives.
The second line of input contains space-separated integers , where the th integer is the colour of the th foot of the scarf.
The next lines each contain two space-separated integers, and , the colour of the first and last foot of the scarf your th relative wants.
Output a single integer , 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
Sample Input 2
3 2 1 2 3 2 5 1 1
Sample Output 2
Sample Input 3
3 1 1 2 3 3 2
Sample Output 3