#include <bits/stdc++.h> using namespace std; #define int long long int n; int p[300400]; inline bool chk3(int l){ if(p[l]<p[l+1]&&p[l+1]<p[l+2])return 0; if(p[l]>p[l+1]&&p[l+1]>p[l+2])return 0; return 1; } bool l3[300400]; int nxt3[300400],pre3[300400]; int nxtmn[300400],nxtmx[300400]; int premn[300400],premx[300400]; int s3[300400]; int ANS[300400]; inline int calc3(int l,int r){ if(r<=2)return 0; int R=r; r=pre3[r-2]; if(l>r)return 0; int len=r-l+1; return len*(R-1)-(s3[r]-s3[l-1]); } set<pair<int,int>>mp; vector<int>g[300400]; vector<pair<int,int>>A[300400]; int L[300400],R[300400]; vector<int>PL[300400],PR[300400]; inline void add(int u,int v){ if(mp.count({u,v}))return ; mp.insert({u,v}); mp.insert({v,u}); g[u].push_back(v); g[v].push_back(u); } int lq[300400],rq[300040]; int t[300400],tw[300400]; inline int lb(int x){return x&-x;} inline void mod(int *t,int x,int k){ while(x<=n)t[x]+=k,x+=lb(x); } inline int gt(int *t,int x){ int res=0; while(x)res+=t[x],x-=lb(x); return res; } int fr[300400]; bool insid[300400]; bool deg[300400]; int cnt=0; inline void change(int x){ if(insid[x])cnt-=deg[x]; insid[x]^=1; if(insid[x])cnt+=deg[x]; } inline void modeg(int x){ if(insid[x])cnt-=deg[x]; deg[x]^=1; if(insid[x])cnt+=deg[x]; } inline void ins(int l,int r){ for(int x:g[r])modeg(x); for(int x:PR[r]) if(L[x]>=l)change(x); } inline void del(int l,int r){ for(int x:g[l])modeg(x); for(int x:PL[l]) if(R[x]<=r)change(x); } inline bool chk(){return cnt==0;} signed main(){ ios::sync_with_stdio(0); cin.tie(0),cout.tie(0); // freopen("SS.in","r",stdin); // freopen("SS.out","w",stdout); cin>>n; for(int i=1;i<=n;i++) cin>>p[i],nxtmn[i]=nxtmx[i]=n+1,premn[i]=premx[i]=0; // return 0; stack<int>mn,mx; for(int i=1;i<=n;i++){ while(!mn.empty()&&p[mn.top()]>p[i]){ nxtmn[mn.top()]=i; mn.pop(); } mn.push(i); while(!mx.empty()&&p[mx.top()]<p[i]){ nxtmx[mx.top()]=i; mx.pop(); } mx.push(i); } while(!mn.empty())mn.pop(); while(!mx.empty())mx.pop(); for(int i=n;i>=1;i--){ while(!mn.empty()&&p[mn.top()]>p[i]){ premn[mn.top()]=i; mn.pop(); } mn.push(i); while(!mx.empty()&&p[mx.top()]<p[i]){ premx[mx.top()]=i; mx.pop(); } mx.push(i); } for(int i=1;i<=n;i++) L[i]=min(premx[i],premn[i]), R[i]=max(nxtmx[i],nxtmn[i]), PL[L[i]].push_back(i), PR[R[i]].push_back(i), add(i,premn[i]),add(i,premx[i]), add(i,nxtmn[i]),add(i,nxtmx[i]); for(int i=1;i<=n;i++) if(i+2<=n&&chk3(i)){ pre3[i]=i; l3[i]=1; } else pre3[i]=pre3[i-1]; nxt3[n+1]=n+1; for(int i=n;i>=1;i--){ if(l3[i])nxt3[i]=i; else nxt3[i]=nxt3[i+1]; } for(int i=1;i<=n;i++) s3[i]=s3[i-1]+nxt3[i]; int r=0; for(int l=1;l<=n;l++){ while(r<=n&&chk()){ r++; if(r<=n) ins(l,r); } fr[l]=r; del(l,r); } // return 0; int q; cin>>q; for(int i=1;i<=q;i++){ int l,r; cin>>l>>r; A[l].push_back({r,i}); lq[i]=l;rq[i]=r; } for(int i=n;i>=1;i--){ mod(tw,fr[i],fr[i]); mod(t,fr[i],1); // cout<<fr[i]<<endl; for(auto e:A[i]){ int id=e.second,r=e.first; // cout<<i<<" "<<r<<" "<<gt(t,r)<<" "<<gt(tw,r)<<endl; ANS[id]=gt(t,r)*(r+1)-gt(tw,r); } } for(int i=1;i<=q;i++) if(ANS[i])cout<<4<<" "<<ANS[i]<<endl; else { int w=calc3(lq[i],rq[i]); if(w)cout<<3<<" "<<w<<endl; else { int len=rq[i]-lq[i]+1; if(len!=1)cout<<2<<" "<<len*(len-1)/2<<endl; else cout<<1<<" "<<1<<endl; } } cout.flush(); return 0; }