记录编号	443543	评测结果	AAAAAAAAAA
题目名称	延绵的山峰	最终得分	100
用户昵称	玉带林中挂	是否通过	通过
代码语言	C++	运行时间	0.623 s
提交时间	2017-08-31 11:58:58	内存使用	84.24 MiB

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
using namespace std;
int max(int a,int b)
{
	return a>b?a:b;
}
inline int read()
{
	int x=0,f=1;
	char ch=getchar();
	while(ch<'0'||ch>'9')
	{
		if(ch=='-')
		f=-1;
		ch=getchar();	
	}
	while(ch>='0'&&ch<='9')
	{
		x=x*10+ch-'0';
		ch=getchar();
	}
	return x*f;
}
const int maxn=1e6+5;
int n,m,p[21],l[maxn],f[maxn][21];

void pre_deal()
{
    for(int i=0;i<=20;i++)
	{
        p[i]=1<<i;
        if(p[i]<=n) l[p[i]]=i;
    }
    for(int i=2,near;i<=n;i++)
	{
        if(l[i]) near=l[i];
        else l[i]=near;
    }
}
void RMQ()
{
    for(int j=1;j<=20;j++)
	{
        for(int i=1;i+p[j]-1<=n;i++)
		{
            f[i][j]=max(f[i][j-1],f[i+p[j-1]][j-1]);
        }
    }
}
int query(int i,int j)
{
    int k=l[j-i+1];
    return max(f[i][k],f[j-p[k]+1][k]);
}
int main()
{
    freopen("climb.in","r",stdin);
    freopen("climb.out","w",stdout);
    n=read();
    for(int i=0;i<=n;i++) f[i][0]=read();
    pre_deal();
    RMQ();
    m=read();
    for(int i=1,x,y;i<=m;i++)
	{
        x=read();y=read();
        if(!x&&!y){puts("0");continue;}
        if(!x) ++x;
        printf("%d\n",query(x,y));
    }
    return 0;
}