#include <bits/stdc++.h>
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
using namespace std;
#define F first
#define S second
using LL = long long;
using i64 = long long;
using pii = pair<int,int>;
using pil = pair<int,i64>;
using pli = pair<i64,int>;
using pll = pair<i64,i64>;
#define str string
// #define mp make_pair
#define eb emplace_back
#define pb push_back
#define si(x) int(x.size())
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define LB lower_bound
#define UB upper_bound
#define i28 __int128
using u32 = unsigned;
using i64 = long long;
using u64 = unsigned long long;
#define ar array

#ifndef ONLINE_JUDGE
#include "/Users/zonghong_0731/template/debug.cpp"
#else
#define debug(...)
#define debugArr(...)
#endif

//for loop
#define rep1(n) for(LL i=0; i<(LL)(n); ++i)
#define rep2(i,n) for(LL i=0; i<(LL)(n); ++i)
#define rep3(i,a,b) for(LL i=(LL)(a); i<(LL)(b); ++i)
#define rep4(i,a,b,c) for(LL i=(LL)(a); i<(LL)(b); i+=(c))
#define cut4(a,b,c,d,e,...) e
#define rep(...) cut4(__VA_ARGS__,rep4,rep3,rep2,rep1)(__VA_ARGS__)
#define per1(n) for(LL i=((LL)n)-1; i>=0; --i)
#define per2(i,n) for(LL i=((LL)n)-1; i>=0; --i)
#define per3(i,a,b) for(LL i=((LL)a)-1; i>=(LL)(b); --i)
#define per4(i,a,b,c) for(LL i=((LL)a)-1; i>=(LL)(b); i-=(c))
#define per(...) cut4(__VA_ARGS__,per4,per3,per2,per1)(__VA_ARGS__)
#define rep_subset(i,s) for(LL i=(s); i>=0; i=(i==0?-1:(i-1)&(s)))

template<class t> using vc=vector<t>;
template<class t> using vvc=vc<vc<t>>;
template<class t> using vvvc = vc<vvc<t>>;

#define vv(type,name,n,...) \
    vector<vector<type>> name(n,vector<type>(__VA_ARGS__))
#define vvv(type,name,n,m,...) \
    vector<vector<vector<type>>> name(n,vector<vector<type>>(m,vector<type>(__VA_ARGS__)))
using vi = vc<int>;
using vl = vc<LL>;

template<typename T> inline bool chmax(T &a, T b) { return ((a < b) ? (a = b, true) : (false)); }
template<typename T> inline bool chmin(T &a, T b) { return ((a > b) ? (a = b, true) : (false)); }

//bit manipulation referenced from maroonrk
template<class T> int topbit(T t){return t==0?-1:63-__builtin_clzll(t);}
template<class T> int botbit(T t){return t==0?64:__builtin_ctzll(t);}
template<class T> int popcount(T t){return __builtin_popcountll(t);}

template<typename T> T gcd(T a,T b) {while (b > 0) {LL t = a % b; a = b; b = t;} return a;}
std::array<i64, 3> exgcd(i64 a, i64 b) {
    if (!b) {
        return {a, 1, 0};
    }
    auto [g, x, y] = exgcd(b, a % b);
    return {g, y, x - a / b * y};
}

template<typename T, typename TT> istream& operator >> (istream& i, pair<T,TT> &p){return i >> p.F >> p.S;}
template<typename T, typename TT> ostream& operator << (ostream& o, const pair<T,TT> &p){return o << p.F << ' ' << p.S;}

//cin vc<T>
template<typename T> istream& operator >> (istream& i, vc<T> &v){for(auto &x: v) i >> x; return i;}

//print 管理
template<typename T> void W(vector<vector<T>>& x){for(auto i: x){ for(auto j: i){cout << j << ' ';} cout << "\n";}}
template<typename T> void W(vector<T>& x){rep(si(x)) cout << x[i] << " \n"[i == si(x) - 1];}
template<typename T> void W(set<T>& x){for(auto i: x) cout << i << ' ';cout << "\n";}
template<typename T> void W(unordered_set<T>& x){for(auto i: x) cout << i << ' ';cout << "\n";}
template<typename T> void W(T && x) {cout << x << "\n";}
template<typename T, typename... S> void W(T && x, S&&... y) {cout << x << ' ';W(y...);}

template<class T> void sort_uni(T& a) {
        sort(all(a));
        a.erase(unique(all(a)), a.end());
}
template<class T> LL MAX(T& a) {
        return ranges::max(a);
}
template<class T> LL MIN(T& a) {
        return ranges::min(a);
}
template<class T> LL SUM(T& a) {
        return reduce(all(a), 0LL);
}

// http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2016/p0200r0.html
template<class Fun> class y_combinator_result {
    Fun fun_;
public:
    template<class T> explicit y_combinator_result(T &&fun): fun_(std::forward<T>(fun)) {}
    template<class ...Args> decltype(auto) operator()(Args &&...args) { return fun_(std::ref(*this), std::forward<Args>(args)...); }
};
template<class Fun> decltype(auto) y_combinator(Fun &&fun) { return y_combinator_result<std::decay_t<Fun>>(std::forward<Fun>(fun)); }

template <class t> using mxheap = priority_queue<t>;
template <class t> using mnheap = priority_queue<t,vc<t>,greater<t>>;

std::mt19937_64 rng(std::chrono::steady_clock::now().time_since_epoch().count());

template<class T>
constexpr T fpow(T a, u64 b, const LL MOD) {
        T res {1};
        while(b) {
                if (b & 1) res = (res * a) % MOD;
                a = (a * a) % MOD;
                b >>= 1;
        }
        return res;
}

const int inf = 1e9;
const LL linf = 2e18;
// BIT 0 base referenced from jiangly
template <typename T>
struct Fenwick {
    int n;
    std::vector<T> a;
    
    Fenwick(int n_ = 0) {
        init(n_);
    }
    
    void init(int n_) {
        n = n_;
        a.assign(n, T{});
    }
    
    void add(int x, const T &v) {
        for (int i = x + 1; i <= n; i += i & -i) {
            a[i - 1] = a[i - 1] + v;
        }
    }
    
    T sum(int x) {
        T ans{};
        for (int i = x; i > 0; i -= i & -i) {
            ans = ans + a[i - 1];
        }
        return ans;
    }
    
    T rangeSum(int l, int r) {
        return sum(r) - sum(l);
    }
    
    int select(const T &k) {
        int x = 0;
        T cur{};
        for (int i = 1 << topbit(n); i; i /= 2) {
            if (x + i <= n && cur + a[x + i - 1] <= k) {
                x += i;
                cur = cur + a[x - 1];
            }
        }
        return x;
    }
};

void tsuyoku_nareru() {
        int n;
        cin >> n;

        Fenwick<int> f(n);
        vi a(n), pos(n);
        rep(n) {
                int x;
                cin >> x;
                a[i] = x - 1;
                pos[a[i]] = i;
                f.add(i, 1);
        }

        int mx = -1;
        per(n) {
                //debug(a[i], i);
                if (a[i] < i) {
                        chmax(mx, a[i]);
                }
        }

        vc<pii> res;
        for (int i = mx; i >= 0; --i) {
                res.pb({i, pos[i]});
        }

        W(mx + 1, si(res));
        int cnt = 0;
        for (auto [x, p] : res) {
                int num = f.sum(p + 1);
                W(num + cnt, 1);
                cnt++;
                f.add(p, -1);
        }






}

int main() {
        ios::sync_with_stdio(false);
        cin.tie(nullptr);
        
        int t = 1;
        // cin >> t;
        while (t--) {
                tsuyoku_nareru();
        }

}