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

constexpr int oo = -1e9;

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_set(T v, int p){
		for(seg[p+=n]=v;p/=2;)seg[p]=S::op(seg[2*p],seg[2*p+1]);
	}
	void update_soma(T v, int p){
		for(seg[p+=n]+=v;p/=2;)seg[p]=S::op(seg[2*p],seg[2*p+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 Soma{using T = int;
	static constexpr T id = 0;
	static T op(T a, T b){return a+b;}
};


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

void solve() {
	int n; cin >> n;
	vi v(n); rep(i,0,n)cin>>v[i];
	rep(i,0,n)v[i]--;
	vi p(n); rep(i,0,n)p[v[i]] = i;
	SegTree<Soma> seg_soma(n+1);
	SegTree<Max> seg_max(n);
	vector<pii> ans; int cost=0;
	vi pref = {v[0]};
	rep(i,1,n){
		if (v[i] > pref.back())pref.pb(v[i]);
		else{
			//debug(v[i]); debug(i);
			seg_max.update_set(v[i], i);
		}
	}
	rep(i,0,n-sz(pref)){
		int x = seg_max.query(0, n-1);
		int u = *upper_bound(all(pref), x);
		//debug(x); debug(p[x]); debug(u);
		int vai = p[u];
		int sai = p[x] + seg_soma.query(0, p[x]);
		seg_soma.update_soma(1, p[u]);
		seg_soma.update_soma(-1, p[x]+1);
		seg_max.update_set(0, p[x]);
		ans.pb({sai, vai}); cost += vai+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();
}