//Linkwish's code
#include<bits/stdc++.h>
#define endl '\n'
#define si inline
#define fi first
#define se second
using namespace std;
typedef long long ll;typedef __int128 li;typedef long double ld;
typedef pair<int,int> pii;typedef pair<ll,ll> pll;
typedef const int ci;typedef const ll cl;ci iinf=INT_MAX;cl linf=LLONG_MAX;
template<typename T>si bool gmax(T &x,const T y){if(x<y)return x=y,1;return 0;}
template<typename T>si bool gmin(T &x,const T y){if(y<x)return x=y,1;return 0;}

namespace LinkWish{
	
	ci N=300005;

	int n,a[N];

	mt19937 R(40094229);
	struct Hoshino{
		int ls,rs,key,sz,fa,v;
		si Hoshino(){ls=rs=sz=fa=0,key=(int)R(),v=0;}
	}t[N];
	int rt;
	si void init(int id){t[id].sz=1,t[id].v=id;}
	si void push_up(int x){
		t[x].sz=t[t[x].ls].sz+t[t[x].rs].sz+1;
		if(t[x].ls!=0)t[t[x].ls].fa=x;
		if(t[x].rs!=0)t[t[x].rs].fa=x;
		t[x].fa=0;
	}
	void splits(int x,int &l,int &r,int k){
		if(x==0)return l=r=0,void();
		if(t[t[x].ls].sz>=k)r=x,splits(t[x].ls,l,t[x].ls,k);
		else l=x,splits(t[x].rs,t[x].rs,r,k-t[t[x].ls].sz-1);
		push_up(x);
	}
	int getrk(int x){
		int res=t[t[x].ls].sz+1;
		for(;t[x].fa!=0;x=t[x].fa)if(x==t[t[x].fa].rs)res+=t[t[t[x].fa].ls].sz+1;
		return res;
	}
	int merge(int x,int y){
		if(!x||!y)return x+y;
		if(t[x].key<t[y].key)return t[x].rs=merge(t[x].rs,y),push_up(x),x;
		return t[y].ls=merge(x,t[y].ls),push_up(y),y;
	}

	void mian(){
		cin>>n;
		for(int i=1;i<=n;i++)cin>>a[i],init(a[i]),rt=merge(rt,a[i]);

		ll ans=0;
		vector<pii> op;
		for(int i=n-1;i;i--){
			int pos=getrk(i),pp=getrk(i+1);
			if(pos>pp){
				ans+=pp,op.emplace_back(pos,pp);
				int x,y,z;
				splits(rt,x,y,pos-1),splits(y,y,z,1);
				rt=merge(x,z);
				splits(rt,x,z,pp-1);
				rt=merge(merge(x,y),z);
			}
		}

		cout<<ans<<' '<<op.size()<<endl;
		for(pii i:op)cout<<i.fi<<' '<<i.se<<endl;
	}
}

signed main(){
	#ifndef ONLINE_JUDGE
	assert(freopen("in.in","r",stdin));
	assert(freopen("out.out","w",stdout));
	#endif
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	LinkWish::mian();
	return 0;
}