#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define int ll
#define endl '\n'
typedef vector<int> vi;
typedef vector<vi> vvi;
#define lowbit(x) x&-x
template <typename T>

struct SegTree
{
    const int START = 1;
    int n;
    struct node
    {
        int l, r;
        T val, lazy;
        int length() const { return (this->r - this->l + 1); }
    };
    std::vector<node> tree;
 
    SegTree() = default;
    SegTree(const std::vector<T>& ini) : n(ini.size() - 1), tree((n + 1) << 2)
    {
        build(1, START, n, ini);
    }
    SegTree(int mx) : n(mx), tree((mx + 1) << 2)
    {
        build(1, START, n);
    }
 
    void _pushup(int u)
    {
        tree[u].val = tree[u << 1].val + tree[u << 1 | 1].val;
    }
 
    void _pushdown(int u)
    {
        const int la = tree[u].lazy;
        if (la)
        {
            tree[u << 1].lazy += la;
            tree[u << 1 | 1].lazy += la;
            tree[u << 1].val += tree[u << 1].length() * la;
            tree[u << 1 | 1].val += tree[u << 1 | 1].length() * la;
            tree[u].lazy = 0;
        }
    }
 
    void build(int u, int l, int r)
    {
        tree[u].l = l;
        tree[u].r = r;
        tree[u].lazy = 0;
        if (l == r)
        {
            tree[u].val = 0;
            return;
        }
        const int mid = (l + r) >> 1;
        build(u << 1, l, mid);
        build(u << 1 | 1, mid + 1, r);
        _pushup(u);
    }
 
    void build(int u, int l, int r, const std::vector<T>& ini)
    {
        tree[u].l = l;
        tree[u].r = r;
        tree[u].lazy = 0;
        if (l == r)
        {
            tree[u].val = ini[l];
            return;
        }
        const int mid = (l + r) >> 1;
        build(u << 1, l, mid, ini);
        build(u << 1 | 1, mid + 1, r, ini);
        _pushup(u);
    }
 
    void _modify(int u, int l, int r, const int s, const int t, T x)
    {
        if (l >= s && r <= t)
        {
            tree[u].val += x * tree[u].length();
            tree[u].lazy += x;
            return;
        }
        const int mid = (l + r) >> 1;
        _pushdown(u);
        if (mid >= s) _modify(u << 1, l, mid, s, t, x);
        if (mid < t) _modify(u << 1 | 1, mid + 1, r, s, t, x);
        _pushup(u);
    }
 
    T _query(int u, int l, int r, const int s, const int t)
    {
        if (l >= s && r <= t)
        {
            return tree[u].val;
        }
        const int mid = (l + r) >> 1;
        _pushdown(u);
        T ans = 0;
        if (mid >= s) ans += _query(u << 1, l, mid, s, t);
        if (mid < t) ans += _query(u << 1 | 1, mid + 1, r, s, t);
        _pushup(u);
        return ans;
    }
 
    void modify(int s, int t, T x) { _modify(1, START, n, s, t, x); }
    T query(int s, int t) { return _query(1, START, n, s, t); }
};

void solve()
{
    int n;
    cin>>n;
    vector<int> a(n+1);
    vi pos(n+1);
    SegTree<int> seg(n+1);
    vi premax(n+1);
    for(int i = 1;i<=n;++i)
    {
        cin>>a[i];
        pos[a[i]] = i;
        premax[i] = max(premax[i-1],a[i]);
    }
    int res = 0;
    vector<pair<int,int>> op(1);
    priority_queue<int> pq;
    int mn = 1e9+10;
    for(int i = 1;i<=n;++i)
    {
        if(premax[i]!=a[i])  
        { 
            pq.push(a[i]);
            mn = min(a[i],mn);
        }
    }
    for(int i = 1;i<=n;++i)
    {
        if(premax[i]==a[i] && pq.size() && a[i]<pq.top())    pq.push(a[i]);
    }
    while(!pq.empty())
    {
        auto p = pq.top();
        pq.pop();
        int coverp = seg.query(pos[p],pos[p]);
        op.emplace_back(pos[p]+coverp,1);
        seg.modify(2,pos[p],1);
        res+=1;
        pos[p] = pos[p+1];
    }
    cout<<res<<" "<<op.size()-1<<endl;
    for(int i = 1;i<=op.size()-1;++i)
    {
        cout<<op[i].first<<" "<<op[i].second<<endl;
    }
}

int32_t main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    int tc = 1;
    while(tc--)
    {
        solve();
    }
    return 0;
}
// 5
// 5 4 2 1 3
// 4 5 2 1 3
// 3 4 5 2 1
// 2 3 4 5 1
// 1 2 3 4 5

// 9
// 2 8 7 3 4 1 9 6 5
// 2 7 8 3 4 1 9 6 5
// 2 6 7 8 3 4 1 9 5
// 2 5 6 7 8 3 4 1 9
// 2 4 5 6 7 8 3 1 9
// 2 3 4 5 6 7 8 1 9
// 1 2 3 4 5 6 7 8 9