记录编号	310765	评测结果	AAAAAAAATT
题目名称	延绵的山峰	最终得分	80
用户昵称	Janis	是否通过	未通过
代码语言	C++	运行时间	2.478 s
提交时间	2016-09-23 10:45:09	内存使用	404.67 MiB

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<vector>
#define MAX(A,B) (A>B?A:B)
using namespace std;

int a[1000005];
//vector<int> a;
int d[1000005][105];
int n,q;
int buf[10];

inline int read()
{
	int x,f=1;
	char ch;
	while(ch=getchar(),!isdigit(ch)){
		if(ch=='-')f=-1;
		if(ch==EOF)return -1;
	}
	x=ch-48;
	while(ch=getchar(),isdigit(ch))x=x*10+ch-48;
	return x*f;
}
inline void writeint(int x){
	int p=0;
	if(x==0) p++;
	else while(x){
			buf[p++]=x%10;
			x/=10;
		}
	for(int i=p-1;i>=0;i--) putchar(buf[i]+'0');
}
void RMQ_init(/*vector<int> &a*//*int a[]*/){
	//int n=a.size();
	for(int i=0;i<n;i++)d[i][0]=a[i];
	for(int j=1;(1<<j)<=n;j++)
		for(int i=0;i+(1<<j)-1<n;i++)
			d[i][j]=MAX(d[i][j-1],d[i+(1<<(j-1))][j-1]);
}
int RMQ_query(int L,int R){
	int k=0;
	while((1<<(k+1))<=R-L+1)k++;
	return max(d[L][k],d[R-(1<<k)+1][k]);
}
void Init(){
	//scanf("%d",&n);
	n=read();
	n++;
	//a.resize(1000000+10);
	for(int i=0;i<n;i++){
		//int temp;
		//scanf("%d",&temp);
		//temp=read();
		//a.push_back(temp);
		a[i]=read();
		//scanf("%d",a[i]);
	}
	RMQ_init();
	//scanf("%d",&q);
	q=read();
	for(int i=0;i<q;i++){
		int A,b;
		//scanf("%d%d",&a,&b);
		A=read(),b=read();
		//printf("%d\n",RMQ_query(A,b));
		writeint(RMQ_query(A,b));
	}
}
int main()
{
	#ifndef DEBUG
		string FileName="climb";
		freopen((FileName+".in").c_str(),"r",stdin);
		freopen((FileName+".out").c_str(),"w",stdout);
	#endif
	Init();
}