#include<bits/stdc++.h>
using namespace std;
#define ll int
#define f(i,a,b) for(ll i=a;i<=b;i++)
#define wt int tt=d;while(tt--)
#define py puts("Yes")
#define pn puts("No")
#define fe(i,e) for(int i=0;i<e.size();i++)
#define vi vector<ll>
inline ll rd() {
	ll x=0,f=1;
	char c=getchar();
	while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
	while(isdigit(c))x=x*10+c-'0',c=getchar();
	return x*f;
}
namespace binom{
	const ll Lim=300010,mod=998244353;
	ll jc[Lim],inv[Lim],inc[Lim];
	void pre(){
		jc[0]=jc[1]=inc[0]=inc[1]=inv[0]=inv[1]=1;
		f(i,2,Lim-1)jc[i]=jc[i-1]*i%mod,inv[i]=(mod-mod/i)*inv[mod%i]%mod,
		inc[i]=inc[i-1]*inv[i]%mod;
	}ll C(ll n,ll m){if(n<0||m<0||n<m)return 0;return jc[n]*inc[m]%mod*inc[n-m]%mod;}
}
// using namespace binom;
ll dx[4]={0,1,0,-1};
ll dy[4]={1,0,-1,0};
#define d rd()
#define pb push_back
const ll N=300010;
struct edge{ll v,w,nx;}e[N<<1];
ll hd[N],cnt;
void add(ll u,ll v,ll w){e[++cnt]=(edge){v,w,hd[u]};hd[u]=cnt;}
ll qp(ll a,ll b,ll p){
	ll ans=1;while(b){
		if(b&1)ans=ans*a%p;
		a=a*a%p;b>>=1;
	}return ans;
}ll n,m;
ll a[300010];
ll t[600010<<2];
#define ls(p) (p<<1)
#define rs(p) (p<<1|1)
void upd(ll p){
    t[p]=(t[ls(p)]+t[rs(p)]);
}void build(ll l,ll r,ll p){
    if(l==r){t[p]=(l>n);return;}
    ll mid=l+r>>1;
    build(l,mid,ls(p));
    build(mid+1,r,rs(p));
    upd(p);
}void add(ll l,ll r,ll p,ll pos,ll v){
    if(l==r){t[p]+=v;return;}
    ll mid=l+r>>1;
    if(mid>=pos)add(l,mid,ls(p),pos,v);
    else add(mid+1,r,rs(p),pos,v);
    upd(p);
}ll ask(ll l,ll r,ll p,ll L,ll R){
    if(l==r)return t[p];
    ll mid=l+r>>1,res=0;
    if(mid>=L)res+=ask(l,mid,ls(p),L,R);
    if(mid<R)res+=ask(mid+1,r,rs(p),L,R);
    return res;
}ll pos[300010];
ll res,x[300010],y[300010];
int main(){
	n=d;f(i,1,n)a[i]=d,pos[a[i]]=i;
    build(1,2*n,1);
    ll P=pos[n];
    for(int i=n-1;i>=1;i--){
        if(pos[i]<P){P=pos[i];continue;}
        else {
            if(P>0)P=0;else P--;
            x[++res]=ask(1,2*n,1,1,pos[i]+n);
            y[res]=1;
            add(1,2*n,1,pos[i]+n,-1);
            add(1,2*n,1,P+n,1);
        }
    }
    cout<<res<<" "<<res<<endl;
    f(i,1,res)cout<<x[i]<<" "<<y[i]<<endl;
	return 0;
}