9
1 2 3 4 5 4 3 2 1
5
3 10
2 5
7 100000000
5 1
3 1