#include <cstdio>namespace Pre{  inline void read(int &sum){    register char ch=getchar();    for(sum=0;ch<‘0‘||ch>‘9‘;ch=getchar());    for(;ch>=‘0‘&&ch<=‘9‘;sum=(sum<<1)+(sum<<3)+ch-‘0‘,ch=getchar());  }  inline int Max(int x,int y){    return x>y?x:y;  }  int a[2017],n;  int Ans[2017];  int St[2017][15],LOG[2017],Bin[15];  inline int get_ans(int l,int r){    int len=r-l+1;    return Max(St[l][LOG[len]],St[r-Bin[LOG[len]]+1][LOG[len]]);  }}namespace Point{  struct point{    int key,pos;    inline friend bool operator < (point a,point b);    inline friend bool operator > (point a,point b);  }A[2017];  inline bool operator < (point a,point b){    return a.key<b.key||(a.key==b.key&&a.pos<b.pos);  }  inline bool operator > (point a,point b){    return b<a;  }}namespace SGT{  const double alpha=0.75;  struct ScapeGoat_Tree{    ScapeGoat_Tree *ch[2];    int size;    Point::point key;    void pushup(){      size=ch[0]->size+ch[1]->size+1;    }    bool isbad(){      return size*alpha+5<ch[0]->size||size*alpha+5<ch[1]->size;    }  }*null,*root,mempool[4020],*stack[4020],*list[4020];  int len,top;  inline void Init(){    null=mempool;    null->ch[0]=null->ch[1]=null;    root=null;    for(int i=1;i<4020;i++)stack[++top]=mempool+i;  }  inline ScapeGoat_Tree *New(Point::point key){    ScapeGoat_Tree *p=stack[top--];    p->ch[0]=p->ch[1]=null;    p->size=1;    p->key=key;    return p;  }  inline void clear(ScapeGoat_Tree *p){    if(p==null)return;    clear(p->ch[0]);    clear(p->ch[1]);    stack[++top]=p;  }  inline void Clear(){    clear(root);    root=null;  }  inline void travel(ScapeGoat_Tree *p){    if(p==null)return;    travel(p->ch[0]);    list[++len]=p;    travel(p->ch[1]);  }  inline ScapeGoat_Tree *divide(int l,int r){    if(l>r)return null;    int mid=(l+r)>>1;    list[mid]->ch[0]=divide(l,mid-1);    list[mid]->ch[1]=divide(mid+1,r);    list[mid]->pushup();    return list[mid];  }  inline void rebuild(ScapeGoat_Tree *&p){    len=0;    travel(p);    p=divide(1,len);  }  inline ScapeGoat_Tree **insert(ScapeGoat_Tree *&p,Point::point key){    if(p==null){      p=New(key);      return &null;    }    p->size++;    ScapeGoat_Tree **ret=insert(p->ch[key>p->key],key);    if(p->isbad())ret=&p;    return ret;  }  inline void Insert(Point::point key){    ScapeGoat_Tree **p=insert(root,key);    if(*p!=null)rebuild(*p);  }  inline Point::point get_kth(int k){    ScapeGoat_Tree *p=root;    while(1)      if(p->ch[0]->size>=k)p=p->ch[0];      else if(p->ch[0]->size+1==k)return p->key;      else k-=p->ch[0]->size+1,p=p->ch[1];  }}namespace PRE_WORK{  void Get_Max(){    using namespace Point;    for(int i=1;i<=Pre::n;i++){      SGT::Clear();      Pre::Ans[i]=Pre::Max(1,Pre::Ans[i]);      SGT::Insert(A[i]);      for(int j=i+1;j<=Pre::n;j++){        SGT::Insert(A[j]);        if(SGT::root->size&1){          int Num=SGT::get_kth((SGT::root->size+1)>>1).pos;          Pre::Ans[Num]=Pre::Max(Pre::Ans[Num],SGT::root->size);        }      }    }  }  void Get_ST(){    using namespace Pre;    Bin[0]=1;    for(int i=1;i<15;i++)Bin[i]=Bin[i-1]<<1;    LOG[0]=-1;    for(int i=1;i<=n;i++)LOG[i]=LOG[i>>1]+1;    for(int i=1;i<=n;i++)St[i][0]=Ans[i];    for(int i=1;Bin[i]<=n;i++)      for(int j=1;j+Bin[i]-1<=n;j++)        St[j][i]=Max(St[j][i-1],St[j+Bin[i-1]][i-1]);  }}namespace Main{  inline void Init(){    SGT::Init();    using Pre::read;    read(Pre::n);    for(int i=1;i<=Pre::n;i++){      read(Pre::a[i]);      Point::A[i]=(Point::point){Pre::a[i],i};    }    PRE_WORK::Get_Max();    PRE_WORK::Get_ST();  }  inline void Work(){    using namespace Pre;    int Q;read(Q);    for(int i=1,l,r;i<=Q;i++){      read(l),read(r);      printf("%d\n",get_ans(l,r));    }  }}int main(){  using namespace Main;  Init(),Work();  return 0;}