DMOPC '20 Contest 2 P2 - Lousy Christmas Presents

View as PDF

Submit solution

Points: 5 (partial)
Time limit: 0.4s
Memory limit: 64M

Problem type

It's almost Christmas time, and you realize you need to start getting presents for your M relatives! The ith 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 ith 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…


Subtask 1 [10%]

1 \le N \le 1\,000
1 \le M \le 1\,000
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 ith integer is the colour of the ith 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 ith 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


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



There are no comments at the moment.