#include<bits/stdc++.h> #define up(i,l,r) for(int i=(l);i<=(r);++i) #define down(i,l,r) for(int i=(l);i>=(r);--i) #define pi pair<int,int> #define p1 first #define p2 second #define m_p make_pair #define p_b push_back using namespace std; typedef long long ll; typedef __uint128_t i128; const int maxn=3e5+10; inline ll read(){ ll x=0;short t=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')t=-1;ch=getchar();} while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar(); return x*t; } int n,q,a[maxn],s[maxn],stk[maxn],tp; int L1[maxn],L2[maxn],R1[maxn],R2[maxn],L[maxn],R[maxn],op[maxn]; int nx2[maxn],nx3[maxn]; vector<int>Gl1[maxn],Gl2[maxn],Gr1[maxn],Gr2[maxn],Gl[maxn]; bool chk(int l,int r){ return (s[r]-s[l]==0||s[r]-s[l]==r-l); } struct BIT { int t[maxn]; BIT(){memset(t,0,sizeof(t));} int lb(int x){return x&(-x);} void upd(int x,int v){for(;x<=n+5;x+=lb(x))t[x]+=v;} int qry(int x){int res=0;for(;x;x-=lb(x))res+=t[x];return res;} }T; int lim; void upd(int x){ //cout<<"upd "<<x<<endl; if(op[x]&&L[x]>=lim)T.upd(R[x],-1); op[x]^=1; if(op[x]&&L[x]>=lim)T.upd(R[x],1); } void slv(){ n=read(); up(i,1,n)a[i]=read();q=read(); up(i,1,n){ while(tp&&a[stk[tp]]>a[i])tp--; L1[i]=stk[tp];stk[++tp]=i; }tp=0;up(i,1,n){ while(tp&&a[stk[tp]]<a[i])tp--; L2[i]=stk[tp];stk[++tp]=i; } stk[tp=0]=n+1; down(i,n,1){ while(tp&&a[stk[tp]]>a[i])tp--; R1[i]=stk[tp];stk[++tp]=i; }tp=0;down(i,n,1){ while(tp&&a[stk[tp]]<a[i])tp--; R2[i]=stk[tp];stk[++tp]=i; } if(n==1){ printf("1\n"); while(q--)printf("1 1\n"); return; }up(i,2,n)s[i]=s[i-1]+(a[i]>a[i-1]); up(i,1,n){ int l=i,r=n+1; while(l+1<r){ int mid=l+r>>1; if(chk(i,mid))l=mid; else r=mid; }nx2[i]=l; } //printf("nx2:");up(i,1,n)printf("%d ",nx2[i]);printf("\n"); int p=1,cnt=0; up(i,1,n) Gl1[L1[i]].p_b(i), Gl2[L2[i]].p_b(i), Gr1[R1[i]].p_b(i), Gr2[R2[i]].p_b(i), L[i]=min(L1[i],L2[i]),R[i]=max(R1[i],R2[i]), Gl[L[i]].p_b(i); up(i,1,n){ lim=i; while(p<=n){ for(int x:Gr1[p])if(x>=i)upd(x),upd(p); for(int x:Gr2[p])if(x>=i)upd(x),upd(p); if(L1[p]>=i&&R2[L1[p]]!=p)upd(p),upd(L1[p]); if(L2[p]>=i&&R1[L2[p]]!=p)upd(p),upd(L2[p]); //cout<<"??? "<<op[1]<<" "<<op[2]<<" "<<op[3]<<endl; //cout<<R[3]<<" "<<L[1]<<endl; if(T.qry(p)){ for(int x:Gr1[p])if(x>=i)upd(x),upd(p); for(int x:Gr2[p])if(x>=i)upd(x),upd(p); if(L1[p]>=i&&R2[L1[p]]!=p)upd(p),upd(L1[p]); if(L2[p]>=i&&R1[L2[p]]!=p)upd(p),upd(L2[p]); break;} p++; } //cout<<"qry: "<<T.qry(p)<<endl; //up(j,1,n)cout<<op[j]<<" "<<R[j]<<endl;cout<<endl; //cout<<op[6]<<" "<<R[6]<<" p: "<<p<<endl; nx3[i]=p-1; for(int x:Gl1[i])if(x<=p)upd(i),upd(x); for(int x:Gl2[i])if(x<=p)upd(i),upd(x); if(R1[i]<=p&&L2[R1[i]]!=i)upd(i),upd(R1[i]); if(R2[i]<=p&&L1[R2[i]]!=i)upd(i),upd(R2[i]); for(int x:Gl[i])if(op[x])T.upd(R[x],-1); //up(j,1,n)cout<<op[j]<<" "<<R[j]<<endl;cout<<endl; } //printf("nx3:");up(i,1,n)printf("%d ",nx3[i]);printf("\n"); if(nx2[1]==n)printf("2\n"); else if(nx3[1]==n)printf("3\n"); else printf("4\n"); up(i,1,q){ int l=read(),r=read(); if(l==r){printf("1 1\n");continue;} if(nx2[l]>=r){printf("2 %lld\n",(r-l+1)*1ll*(r-l)/2);continue;} if(nx3[l]>=r){ ll res=0; up(i,l,r)if(nx2[i]<r)res+=r-nx2[i]; printf("3 %lld\n",res);continue; }ll res=0; up(i,l,r)if(nx3[i]<r)res+=r-nx3[i]; printf("4 %lld\n",res); } } int main(){ //freopen("color.in","r",stdin); //freopen("color.out","w",stdout); slv(); fclose(stdin); fclose(stdout); return 0; }