3. 延绵的山峰

【题目描述】

有一座延绵不断、跌宕起伏的山，最低处海拔为0，最高处海拔不超过8848米，从这座山的一端走到另一端的过程中，每走1米海拔就升高或降低1米。有$q$个登山队计划在这座山的不同区段登山，当他们攀到各自区段的最高峰时，就会插上队旗。请你写一个程序找出他们插旗的高度。

【输入格式】

第1行，一个整数$n(1\leq n\leq 10^6)$，表示山两端的跨度。

接下来$n+1$行，每行一个非负整数$h_i$，表示该位置的海拔高度，其中$h_0=h_n=0$。

然后是一个正整数$1(1\leq q\leq 7000)$，表示登山队的数量。

接下来$q$行，每行两个数$a_i,b_i$，表示第$i$个登山队攀爬的区段$[a_i,b_i]$，其中$0\leq a_i\leq b_i\leq n$。

【输出格式】

输出共$q$行，每行为一个整数，表示第$i$个登山队插旗的高度。

【输入样例】

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

【输出样例】

4
3
4
3
2