Input:

7
1 1 1 1 1 1 1
1 2
1 3
1 4
1 5
2 6
2 7
9
1 1
1 1
1 1
1 1
1 1
1 6
2 2
1 2
2 7

output:
7
8

I used segment tree, but got wa on testcase 6