#include<bits/stdc++.h> using namespace std; #define int long long #define inx(u) int I=h[(u)],v=edge[I].v;I;I=edge[I].nx,v=edge[I].v int read(){int x=0,f=1;char c=getchar();while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();return x*f;} const int MAXN=2010; struct Edge{int v,nx;}edge[MAXN];int h[MAXN],CNT;void add_side(int u,int v){ edge[++CNT]={v,h[u]};h[u]=CNT;edge[++CNT]={u,h[v]};h[v]=CNT;} int n,m,k,a[MAXN],lst[MAXN],nxt[MAXN],f[MAXN][MAXN]; stack<int>st1,st2; int L,R,ans; void dfs(int now,int sum){ if(sum>=ans)return; if(now==R+1){ ans=sum; return; } for(int i=1;i<=sum+1;i++){ bool fl=0; for(inx(now)){fl|=a[v]==i;} if(!fl){ a[now]=i; dfs(now+1,sum+(i==sum+1)); a[now]=0; } } } void slv(){ n=read(); for(int i=1;i<=n;i++)a[i]=read(); for(int i=1;i<=n;i++){ for(int j=i;j>=1;j--)if(a[j]<a[i]){add_side(j,i);break;} for(int j=i;j>=1;j--)if(a[j]>a[i]){add_side(j,i);break;} for(int j=i;j<=n;j++)if(a[j]<a[i]){add_side(j,i);break;} for(int j=i;j<=n;j++)if(a[j]>a[i]){add_side(j,i);break;} } for(int i=1;i<=n;i++)a[i]=0; for(int i=1;i<=n;i++){ for(int j=i;j<=n;j++){ L=i,R=j; ans=R-L+1; dfs(i,0); f[L][R]=ans; } } printf("%lld\n",f[1][n]); m=read(); while(m--){ int l=read(),r=read(),res=0,cnt=0; for(int i=l;i<=r;i++){ for(int j=i;j<=r;j++){ if(f[i][j]>res)res=f[i][j],cnt=0; if(f[i][j]==res)cnt++; } } printf("%lld %lld\n",res,cnt); } } signed main(){ slv(); return 0; }