比赛场次	315
比赛名称	Segment Tree Competition
比赛状态	已结束比赛成绩
开始时间	2016-08-28 19:00:00
结束时间	2016-08-28 22:00:00
开放分组	全部用户
注释介绍

题目名称	延绵的山峰
输入输出	`climb.in/out`
时间限制	1000 ms (1 s)
内存限制	512 MiB
测试点数	10 简单对比

用户	结果	时间	内存	得分
AntiLeaf	AAAAAAAAAA	0.398 s	1.56 MiB	100
ZXCVBNM_1	AAAAAAAAAA	0.428 s	49.91 MiB	100
Ostmbh	AAAAAAAAAA	0.438 s	17.45 MiB	100
_Itachi	AAAAAAAAAA	0.533 s	61.33 MiB	100
NewBee	AAAAAAAAAA	0.547 s	17.43 MiB	100
浮生随想	AAAAAAAAAA	0.551 s	14.01 MiB	100
Hzoi_Yniverse	AAAAAAAAAA	0.551 s	17.45 MiB	100
Yuri	AAAAAAAAAA	0.554 s	15.55 MiB	100
SOBER GOOD BOY	AAAAAAAAAA	0.562 s	46.14 MiB	100
灰里城	AAAAAAAAAA	0.563 s	15.57 MiB	100
Respawn	AAAAAAAAAA	0.565 s	14.02 MiB	100
农场主	AAAAAAAAAA	0.579 s	49.88 MiB	100
GROWL GOOD BOYส็	AAAAAAAAAA	0.657 s	36.91 MiB	100
哒哒哒哒哒！	AAAAAAAAAA	0.704 s	46.09 MiB	100
Steve	AAAAAAAAAA	0.809 s	15.57 MiB	100
Sky_miner	AAAAAAAAAA	0.855 s	15.57 MiB	100
YGOI_真神名曰驴蛋蛋	AAAAAAAAAA	0.887 s	30.77 MiB	100
可以的.	AAAAAAAAAA	1.259 s	15.57 MiB	100
Hzoi_Queuer	AAAAAAAAAA	1.286 s	12.44 MiB	100
半汪	AAAAAAAAAA	1.812 s	14.01 MiB	100
Twist Fate	AAAAAAAATT	2.059 s	1.29 MiB	80
Hzoi_chairman	AAAAAAAATT	2.111 s	30.95 MiB	80
Tiny	AAAAAAAATT	2.212 s	80.42 MiB	80
沉迷学习的假的Keller	AAAAAAAATT	2.225 s	80.42 MiB	80
FoolMike	AAAAAAAATT	2.235 s	76.58 MiB	80
派特三石	AAAAAAAATT	2.237 s	80.43 MiB	80
洛克索耶夫	AAAAAAAATT	2.265 s	89.56 MiB	80
森林	AAAAAAAATT	2.308 s	103.28 MiB	80
Hzoi_Go灬Fire	AAAAAAAATT	2.318 s	106.69 MiB	80
Go灬Fire	AAAAAAAATT	2.327 s	118.55 MiB	80
宋逸群	AAAAAAAATT	2.343 s	175.39 MiB	80
零度阳光	AAAAAAAATT	2.853 s	4.10 MiB	80

延绵的山峰

★★ 输入文件：climb.in 输出文件：climb.out 简单对比
时间限制：1 s 内存限制：512 MiB

【题目描述】

有一座延绵不断、跌宕起伏的山，最低处海拔为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$个登山队插旗的高度。

【输入样例】

【输出样例】