Input
5
1 3 2 4 2
4
1 5
2 5
3 5
4 5
Output
4
4
1
1