#include<bits/stdc++.h>

#define int long long
#define endl '\n'
#define rep(i,a,b) for(int i=(int)(a);i<(int)(b);i++)
#define pb push_back
#define eb emplace_back
#define debug(x) ; //cout << #x << ": " << x << endl
#define sz(x) (int)((x).size())
#define all(x) x.begin(), x.end()
#define esp ' '
#define pii pair<int,int>
#define vi vector<int>

using namespace std;

template<class S>
struct SegTree{ using T = S::T;
	int n; vector<T> seg;
	SegTree(int s):n(s),seg(2*n,S::id){}
	void update(T v, int p){
		for(seg[p+=n]=v;p/=2;)seg[p]=S::op(seg[p/2],seg[p/2+1]);
	}
	T query(int l, int r){
		T vl=S::id, vr=S::id;
		for(l+=n,r+=n+1;l<r;l/=2,r/=2){
			if (l&1)vl = S::op(vl, seg[l++]);
			if (r&1)vr = S::op(seg[--r], vr);
		}
		return S::op(vl, vr);
	}
};

struct Spec{using T = int;
	static constexpr T id = 0;
	static T op(T a, T b){return a+b;}
};

void solve() {
	int n; cin >> n;
	vi v(n); rep(i,0,n)cin>>v[i];
	rep(i,0,n)v[i]--;
	SegTree<Spec> seg(n+1);
	vector<pii> ans; int cost=0;
	vi order;
	vector<pii> info(n);
	priority_queue<int> pq;
	for(int i = n-1, pos = n-1; i >= -1; i--){
		
		while(not pq.empty() and pq.top()==pos){
			int x = pq.top(); pq.pop();
			debug("cara descendo");
			debug(pos); debug(x);
			info[x].second = i+1; pos--;
		}
		if (i==-1)continue;
		debug("cara atual");
		debug(pos); debug(v[i]);
		if (v[i]==pos){
			debug("cara certo");
			debug(pos); debug(v[i]);
			pos--; continue;
		}
		else{
			debug("cara subindo");
			debug(pos); debug(v[i]);
			order.pb(v[i]); pq.push(v[i]); info[v[i]].first = pos;
		}
	}
	for(int x : order){
		ans.pb(info[x]); cost += info[x].second+1;
	}
	cout << cost << esp << sz(ans) << endl;
	for(auto [a, b] : ans)cout << a+1 << esp << b+1 << endl;
}

signed main() {
	ios_base::sync_with_stdio(0);cin.tie(0);

	int t=1;
	//cin>>t;
	while(t--) solve();
}