100.0% (9/9)

69.2% (9/13)

# Sample Input

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

16
9
55
5
35

# Hints

1(0~2)$N \le 10 ^ 3, Q \le 10 ^ 3$40
2(3~4)$N \le 10 ^ 5, Q \le 10 ^ 5$7
3(5~7)53

# Problem Source

Problem set by 魔法師(Polarz)