RMQ问题

时间限制: 1000 ms 内存限制: 65536 kb
总通过人数: 212 总提交人数: 224

题目描述

给定长度为N的序列,M个询问,每次询问两个数字A,B,要求求出属于A到B这段区间内的最大数。

输入

一个整数N表示数字的个数,接下来一行为N个数。第三行读入一个M,表示你看完那串数后需要被提问的次数,接下来M行,每行都有两个整数A,B。

输出

输出共M行,每行输出一个数。

输入样例

6 
34 1 8 123 3 2 
4 
1 2 
1 5 
3 4 
2 3 

输出样例

34 
123 
123 
8 

HINT

对40%:$N \le 6000, M \le 500 $

对100%: $ N \le 200000, M \le 10000$,

所有数均在int范围内

相关推荐