将RMQ递推公式修改下，best[i][j]=max(best[i-1][j],best[i-1][j+(1<<(i-1)),j-1+(1<<(i-1))向两边最多能扩展的长度,j+(1<<(i-1))向两边最多能扩展的长度)
求向两边最多能扩展的长度要用二分搜索来实现，然后最好能将检索的结果记录在数组中，如果下次进行同样的检索直接查表（如果不进行这样的处理C++1500ms能过，G++就TLE了），详细的看代码吧，我代码应该写的很清楚了



Source Code

Problem: 3368  User: yzhw 
Memory: 8688K  Time: 594MS 
Language: C++  Result: Accepted 

Source Code 
# define maxn 100005
# include <cstdio>
# include <cstring>
int RMQ[maxn],mm[maxn];
int best[20][maxn];
int minrefer[maxn*2],maxrefer[maxn*2];
int min(int a,int b)
{
    return a<b?a:b;
}

inline int max(int a,int b)
{
    return a>b?a:b;
}
inline int max(int a,int b,int c,int d)
{
    return max(max(a,b),max(c,d));
}
int low(int n,int pos)
{
    if(minrefer[pos+100000])
      return minrefer[pos+100000];
    int s=1,e=n;
    while(s<=e)
    {
      int mid=(s+e)/2;
      if(pos<=RMQ[mid])
        e=mid-1;
      else
        s=mid+1;
    }
    minrefer[pos+100000]=s;
    return s;
}
int high(int n,int pos)
{
    if(maxrefer[pos+100000])
      return maxrefer[pos+100000];
    int s=1,e=n;
    while(s<=e)
    {
      int mid=(s+e)/2;
      if(pos>=RMQ[mid])
        s=mid+1;
      else
        e=mid-1;
    }
    maxrefer[pos+100000]=e;
    return e;
}
    
void initRMQ(int n)
{
     int i,j,a,b;
     for(mm[0]=-1,i=1;i<=n;i++)
     mm[i]=((i&(i-1))==0)?mm[i-1]+1:mm[i-1];
     for(i=1;i<=n;i++) best[0][i]=1;
     for(i=1;i<=mm[n];i++)
     for(j=1;j<=n+1-(1<<i);j++)
     {
       a=best[i-1][j];
       b=best[i-1][j+(1<<(i-1))];
       best[i][j]=max(a,b,min(j+(1<<(i))-1,high(n,RMQ[j+(1<<(i-1)-1)]))-max(low(n,RMQ[j+(1<<(i-1))-1]),j)+1,min(j+(1<<(i))-1,high(n,RMQ[j+(1<<(i-1))]))-max(low(n,RMQ[j+(1<<(i-1))]),j)+1);
     }
     return;
}
int askRMQ(int a,int b,int n)
{
    int t;
    int oa=a,ob=b;
    t=mm[b-a+1];b-=(1<<t)-1;
    a=best[t][a];b=best[t][b];
    return max(a,b,min(ob,high(n,RMQ[oa+(1<<t)-1]))-max(low(n,RMQ[oa+(1<<t)-1]),oa)+1,min(ob,high(n,RMQ[ob-(1<<t)+1]))-max(low(n,RMQ[ob-(1<<t)+1]),oa)+1);
}
int main()
{
  //  freopen("frequent.in","r",stdin);
  //  freopen("ans.txt","w",stdout);
    while(true)
    {
       int n,q;
       scanf("%d",&n);
       if(!n) break;
       scanf("%d",&q);
       for(int i=1;i<=n;i++)
         scanf("%d",RMQ+i);
       memset(minrefer,0,sizeof(minrefer));
       memset(maxrefer,0,sizeof(maxrefer));
       initRMQ(n);
       
       for(int i=1;i<=q;i++)
       {
          int a,b;
          scanf("%d%d",&a,&b);
          printf("%d\n",askRMQ(a<b?a:b,a>b?a:b,n));
       }
    }
    return 0;
}