题目来自COGS
绵延延绵的山峰这道题啊，裸的线段树，并不知道为什么就算到两星半的难度了。。
即使是一道水题，并不排除用高级算法解决来刷rank。
这几天我大致研究了一下zkw线段树，不得不说，从下到上的线段树就是快啊，膜拜神犇zkw，我是蒟蒻orz….
代码已经用了所有我能想到的常数优化，然而依然不是rank1，这就很尴尬了。。。

#include <iostream>
#include <cstdio>
#include <algorithm>
#define MX 1000010
using namespace std;
int tree[MX<<2];
int n, q, x, y, m, a;
inline int get_num()
{
	int ans=0;
	char tmp;
	while(tmp<'0'||tmp>'9')	tmp=getchar();
	while(tmp>='0'&&tmp<='9')
	{
		ans=ans*10+tmp-48;
		tmp=getchar();
	}
	return ans;
}
int main()
{
	//freopen("climb.in","r",stdin);
	//freopen("climb.out","w",stdout);
	n=get_num();
	for(m=1;m<n+2;m<<=1);
	n++;
	for(int i=1;i<=n;i++)
	{
		tree[i+m]=get_num();
	}
	for(int i=m-1;i>=1;i--)
		tree[i]=max(tree[i<<1],tree[(i<<1)^1]);
	q=get_num();
	for(int i=1;i<=q;i++)
	{
		x=get_num()+1;y=get_num()+1;
		a=0;
		x=x+m-1;
		y=y+m+1;
		for(;x^y^1;x>>=1,y>>=1)
		{
			if(!(x&1))
				a=max(a,tree[x^1]);
			if(y&1)
				a=max(a,tree[y^1]);
		}
		cout<<a<<"\n";
	}
	return 0;
}