#include <bits/stdc++.h>
using namespace std;
const int N=3e5+5;
int n,j=1,a[N],b[N];
vector<array<int,2>> p;
long long s;
int main(){
	cin.tie(0)->sync_with_stdio(0);
	cin>>n;
	for(int i=1;i<=n;i++) cin>>a[i];
	for(int i=1;i<=n;i++){
		for(;j<=n&&a[j]<i;j++) p.push_back({i-1,b[a[j]]});
		if(i==a[j]) j++;
		else s+=b[i]=j;
	}
	for(;j<=n;j++) p.push_back({n,b[a[j]]});
	cout<<s<<" "<<p.size()<<"\n";
	reverse(begin(p),end(p));
	for(auto&x:p) cout<<x[0]<<" "<<x[1]<<"\n";
	return 0;
}