记录编号	126877	评测结果	AAAAAAAAAA
题目名称	延绵的山峰	最终得分	100
用户昵称	ztx	是否通过	通过
代码语言	C++	运行时间	1.789 s
提交时间	2014-10-14 14:34:52	内存使用	80.40 MiB

/*
	author :hzoi_ztx
	title  :cogs 58. 延绵的山峰 
	ALG    :RMQ
	comment: 默写 = =  

*/

#include <cstdio>

#define  maxn  1000010
#define  maxk  21

int n , Q ;

int d[maxn][maxk] = {0} ;

inline int max(int a , int b) { return a > b ? a : b ; }

int main() {
	#define READ
	#ifdef  READ
		freopen("climb.in" ,"r",stdin ) ;
		freopen("climb.out","w",stdout) ;
	#endif
	int i , k , x , y ;
	
	scanf("%d", &n ) ;
	for (i = 0 ; i <= n ; i ++ )
		scanf("%d", &d[i][0] ) ;
	
	for (k = 1 ; (1<<k) <= n ; k ++ )
		for (i = 0 ; i+(1<<k)-1 <= n ; i ++ )
			d[i][k] = max(d[i][k-1] , d[i+(1<<(k-1))][k-1]) ;
	
	scanf("%d", &Q ) ;
	while ( Q -- ) {
		scanf("%d%d", &x , &y ) ;
		for (k = 0 ; (1<<(k+1)) < (y-x+1) ; k ++ ) ;
		printf("%d\n", max(d[x][k] , d[y-(1<<k)+1][k])) ;
	}
	return 0 ;
}