#include<iostream>
#include<vector>
#include<utility>
using namespace std;
int n;
int v[300005];
int pos[300005];
int af[300005];
int tag[300005];

struct Node{
    int l, r, val;
}node[1200000];

void push_up(int id){
    if(node[id].l == node[id].r) return;
    node[id].val = node[id*2].val + node[id*2+1].val;
}

void build(int id, int l, int r){
    node[id].l = l;
    node[id].r = r;
    if(l == r) return;
    int mid = (l + r) / 2;
    build(id*2, l, mid);
    build(id*2+1, mid+1, r);
}

int qr(int id, int l, int r){
    if(node[id].l >= l && node[id].r <= r){
        return node[id].val;
    }
    if(node[id].l > r || node[id].r < l) return 0;
    return qr(id*2, l, r) + qr(id*2+1, l, r);
}

void modify(int id, int p, int x){
    if(node[id].l == node[id].r){
        node[id].val = x;
        return;
    }
    int mid = (node[id].l + node[id].r) / 2;
    if(p <= mid){
        modify(id*2, p, x);
    }
    else{
        modify(id*2+1, p, x);
    }
    push_up(id);
}

void solve(){
    build(1, 0, n);
    for(int i = 1;i <= n;i++) pos[v[i]] = i;
    for(int i = n;i >= 2;i--){
        if(pos[i] > pos[i - 1]){
            tag[pos[i]] = 1;
            tag[pos[i - 1]] = 1;
        }
        else{
            break;
        }
    }
    for(int i = n;i >= 1;i--){
        af[i] = qr(1, v[i] + 1, n);
        if(tag[i] == 0) modify(1, v[i], 1);
    }
    int cost = 0;
    vector<pair<int, int> > ans;
    for(int i = n;i >= 1;i--){
        if(tag[pos[i]]) continue;
        int x = pos[i] + af[pos[i]];
        int y = 1;
        if(x == y) continue;
        ans.push_back(pair<int, int>(x, y));
        cost++;
    }
    cout << cost << ' ' << ans.size() << '\n';
    for(pair<int, int> pr : ans) cout << pr.first << ' ' << pr.second << '\n';
}

int main(){
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cin >> n;
    for(int i = 1;i <= n;i++) cin >> v[i];
    solve();
    return 0;
}