#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=6e5+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 { ll t[maxn]; BIT(){memset(t,0,sizeof(t));} int lb(int x){return x&(-x);} void upd(int x,ll v){for(;x<=n+5;x+=lb(x))t[x]+=v;} ll qry(int x){ll res=0;for(;x;x-=lb(x))res+=t[x];return res;} }T,T1,T2,T3,T4; 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); } ll ans1[maxn],ans2[maxn],res[maxn],RR[maxn]; ll F[maxn]; vector<pi>Q1[maxn],Q2[maxn]; 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=0,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){ if(T.qry(p))break;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]); //cout<<"??? "<<op[1]<<" "<<op[2]<<" "<<op[3]<<endl; //cout<<R[3]<<" "<<L[1]<<endl; } //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){ans1[i]=ans2[i]=1;continue;} if(nx2[l]>=r){ans1[i]=2,ans2[i]=(r-l+1)*1ll*(r-l)/2;continue;} RR[i]=r; if(nx3[l]>=r){ ans1[i]=3; Q1[r].p_b(m_p(r,i+q));Q1[l-1].p_b(m_p(r,-(i+q))); Q1[r].p_b(m_p(r,i));Q1[l-1].p_b(m_p(r,-i)); /*ll res=0; up(i,l,r)if(nx2[i]<r)res+=r-nx2[i]; printf("3 %lld\n",res);*/ continue; }ans1[i]=4; Q2[r].p_b(m_p(r,i+q));Q2[l-1].p_b(m_p(r,-(i+q))); Q2[r].p_b(m_p(r,i));Q2[l-1].p_b(m_p(r,-i)); /*ll res=0; up(i,l,r)if(nx3[i]<r)res+=r-nx3[i]; printf("4 %lld\n",res);*/ } up(i,1,n){ T1.upd(nx2[i],1),T2.upd(nx2[i],-nx2[i]); T3.upd(nx3[i],1),T4.upd(nx3[i],-nx3[i]); for(auto it:Q1[i]){ int s=it.p2/abs(it.p2);ll v=0;int id=abs(it.p2); if(id>q)v=T1.qry(it.p1);else v=T2.qry(it.p1); res[id]+=s*v; } for(auto it:Q2[i]){ int s=it.p2/abs(it.p2);ll v=0;int id=abs(it.p2); if(id>q)v=T3.qry(it.p1);else v=T4.qry(it.p1); res[id]+=s*v; } }up(i,1,q)if(RR[i])res[i]=res[i+q]*1ll*RR[i]+res[i]; up(i,1,q)if(RR[i])ans2[i]=res[i]; up(i,1,q)printf("%lld %lld\n",ans1[i],ans2[i]); } int main(){ //freopen("color.in","r",stdin); //freopen("color.out","w",stdout); slv(); fclose(stdin); fclose(stdout); return 0; }