记录编号	437644	评测结果	AAAAAAAAAA
题目名称	延绵的山峰	最终得分	100
用户昵称	~玖湫~	是否通过	通过
代码语言	C++	运行时间	0.349 s
提交时间	2017-08-14 14:17:39	内存使用	61.35 MiB

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
using namespace std;
const int M=1000000+10;
int n,m,cnt;
int rt[4*M],lc[4*M],rc[4*M],mx[4*M];
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;
}
void update(int pos,int zhi,int &rt,int l,int r){
	if(!pos) return ;
	if(!rt) rt=++cnt;
	mx[rt]=max(mx[rt],zhi);
	if(l==r) return ;
	int mid=l+r>>1;
	if(pos<=mid) update(pos,zhi,lc[rt],l,mid);
	else         update(pos,zhi,rc[rt],mid+1,r);
}
int query(int s,int t,int &rt,int l,int r){
	if(!rt) return 0;
	if(s<=l&&r<=t) return mx[rt];
	int mid=l+r>>1; int res=1<<31;
	if(s<=mid) res=max(res,query(s,t,lc[rt],l,mid));
	if(t>mid)  res=max(res,query(s,t,rc[rt],mid+1,r));
	return res;
}
int main(){
	freopen("climb.in","r",stdin);
	freopen("climb.out","w",stdout);
	n=read();int aa,bb;
	for(int i=0;i<=n;i++){
		aa=read();
		update(i,aa,rt[1],1,n);
	}
	//cout<<"sdf "<<endl;
	m=read();
	for(int i=1;i<=m;i++){
		aa=read();bb=read();
		printf("%d\n",query(aa,bb,rt[1],1,n));
	}
	return 0;
}