Input
5 3
1 1 2 3 2
1 5
2 4
3 5
Output
1
-1
2
Input
6 5
1 2 1 3 2 3
4 6
1 3
2 5
2 4
1 6
Output
2
2
3
-1
2