记录编号	60508	评测结果	AAAAAAAAAA
题目名称	延绵的山峰	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	1.770 s
提交时间	2013-05-26 10:39:25	内存使用	80.42 MiB

#include<iostream>
#include<cstdio>
#include<iomanip>
#include<map>
#include<set>
#include<vector>
#include<cstring>
#include<queue>
#include<deque>
#include<algorithm>
#include<cmath>
using namespace std;
const int SIZEN=1000010,SIZEM=20;
int n;
int h[SIZEN]={0};//要求RMQ的数组
int f[SIZEN][SIZEM]={0};//ST算法
void ST_init(int a[SIZEN]){
	int m=floor(log((double)n)/log(2.0));//不大于n的最大2的幂
	int i,j;
	for(i=0;i<=n;i++) f[i][0]=a[i];
	for(j=1;j<=m;j++){
		for(i=0;i<=n;i++){
			if(i+(1<<(j-1))-1>n) continue;
			f[i][j]=max(f[i][j-1],f[i+(1<<(j-1))][j-1]);
		}
	}
}
int rmq(int l,int r){
	int m=floor(log((double)(r-l+1))/log(2.0));
	return max(f[l][m],f[r-(1<<m)+1][m]);
}
void read(void){
	scanf("%d",&n);
	int i;
	for(i=0;i<=n;i++) scanf("%d",&h[i]);
}
int main(){
	freopen("climb.in","r",stdin);
	freopen("climb.out","w",stdout);
	read();
	ST_init(h);
	int Q,l,r;
	int i;
	scanf("%d",&Q);
	for(i=1;i<=Q;i++){
		scanf("%d%d",&l,&r);
		printf("%d\n",rmq(l,r));
	}
	return 0;
}