//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;
		si Hoshino(){ls=rs=sz=fa=0,key=(int)R();}
	}t[N];
	int rt;
	si void init(int id){t[id].sz=1;}
	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;
		auto Move=[&](int pos,int pp){
			op.emplace_back(pos,pp),ans+=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);
		};
		
		vector<pii> q;
		for(int i=1;i<n;i++){
			int pos=getrk(i),pp=getrk(i+1);
			if(pp<pos)q.emplace_back(pp,i);
		}
		sort(q.begin(),q.end(),greater<pii>());
		for(pii i:q){
			int pos=getrk(i.se),pp=getrk(i.se+1);
			assert(pp<pos);
			Move(pos,pp);
		}

		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;
}