一，介绍
ST算法是一个用倍增来求区间最值的算法，倍增是一个与二分类似的思想的一个东西，倍增简而言之也就是区间长度按1，2，4，8.....
我们先用nlog(n)的复杂度打出一个最大值表，后面我们可以通过O（1）的 复杂度来直接得出最大值
二,思路
我们用到F[i][j]
这个含义代表 [i,i+2^j-1]这一段区间的最大值，F[i][j]=max(F[i][j-1],F[i+(1<<(j-1))][j-1]),也就是我拆分成两个区间来求最大值
F[i][0]=a[i];
我们求最大值，因为我们是按倍增的长度来的，我们只要求出最接近当前区间长度的倍增，然后max（F[l,k],F[r-(1<<k)+1,k]）即可,因为
我们两个端点往里延申，我们就能覆盖掉当前区间，又不会超出区间，因为我们是求区间最大值，中间区间重复地方我们可以不用管，只需要覆盖到了当前区间且
没有覆盖到其他区间即可
#include<bits/stdc++.h>
#define mod 1000000007
#define maxn 1005
using namespace std;
typedef long long ll;
ll t,n,m,a[maxn];
ll f[maxn][];
void build(){
ll t=log(n)/log()+;
for(int i=;i<=n;i++) f[i][]=a[i];
for(int j=;j<t;j++){
for(int i=;i<=n-(<<j)+;i++){
f[i][j]=max(f[i][j-],f[i+(<<(j-))][j-]);
}
}
}
ll query(ll l,ll r){
ll k=log(r-l+)/log();
printf("%lld\n",max(f[l][k],f[r-(<<k)+][k]));
}
int main()
{
scanf("%lld",&t);
while(t--)
{
scanf("%lld",&n);
for(int i=;i<=n;i++){
scanf("%lld",&a[i]);
}
build();
scanf("%lld",&m);
ll l,r;
for(int i=;i<m;i++){
scanf("%lld%lld",&l,&r);
query(l,r);
}
}
}