记录编号	443531	评测结果	AAAAAAAAAA
题目名称	延绵的山峰	最终得分	100
用户昵称	Regnig Etalsnart	是否通过	通过
代码语言	C++	运行时间	0.291 s
提交时间	2017-08-31 10:30:16	内存使用	11.73 MiB

#include<cstdio>
using namespace std;
const int maxn=1000010;
int n,q,h[maxn],maxv[2*maxn],ql,qr;
int max(int a,int b)
{
	return a>b?a:b;
}
void build(int now,int l,int r)
{
	if(l==r)
	{
		maxv[now]=h[l];
		return;
	}
	else
	{
		int mid=l+(r-l)/2;
		build(now*2,l,mid);
		build(now*2+1,mid+1,r);
		maxv[now]=max(maxv[now*2],maxv[now*2+1]);
	}
}
int query(int now,int l,int r)
{
	if(r<ql||l>qr)return 0;
	int ans=0,mid=l+(r-l)/2;
	if(l>=ql&&r<=qr)return maxv[now];
	if(mid>=ql)ans=max(ans,query(now*2,l,mid));
	if(mid<qr)ans=max(ans,query(now*2+1,mid+1,r));
	return ans;
}
int main()
{
	freopen("climb.in","r",stdin);freopen("climb.out","w",stdout);
	scanf("%d",&n);
	for(int i=1;i<=n+1;i++)scanf("%d",&h[i]);
	build(1,1,n+1);
	scanf("%d",&q);
	while(q--)
	{
		scanf("%d%d",&ql,&qr);
		ql++;qr++;
		printf("%d\n",query(1,1,n+1));
	}
	return 0;
}