#include <bits/stdc++.h>
using namespace std;
const int maxn = 3e5 + 10;
int n;
struct tree
{
    int c[maxn];
    int lowbit(int x) { return x & (-x); }
    void update(int x, int k)
    {
        while (x <= n)
        {
            c[x] += k;
            x += lowbit(x);
        }
    }
    int getsum(int x)
    {
        int res = 0;
        while (x > 0)
        {
            res += c[x];
            x -= lowbit(x);
        }
        return res;
    }
} tri;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n;
    vector<int> a(n + 1), id(n + 1);
    for (int i = 1; i <= n; i++)
        cin >> a[i], id[a[i]] = i;
    int p = 1;
    for (int i = n; i >= 1; i--)
        if (a[i] != i)
        {
            p = i;
            break;
        }
    vector<pair<int, int>> ans;
    for (int i = 1; i <= n; i++)
        tri.update(i, 1);
    for (int i = p - 1; i >= 1; i--)
    {
        ans.emplace_back(tri.getsum(id[i]) + p - 1 - i, 1);
        tri.update(id[i], -1);
    }
    cout << p - 1 << " " << ans.size() << "\n";
    for (auto [x, y] : ans)
        cout << x << " " << y << "\n";
}