D

#include <bits/stdc++.h>
using namespace std;

#define ll     long long
#define _test   int _TEST; cin>>_TEST; while(_TEST--)
#define ff     first
#define ss     second
#define pb     push_back

vector<pair<int, int>> op;

void func2(vector<int>& a, int l, int r)
{
    if (l == r)
    {
        if (a[l] != 0)
    {
            op.push_back({l, l});
            a[l] = 0;
        }
        return;
    }

    func2(a, l + 1, r);
    if (a[l] != r - l)
    {
        op.push_back({l, r});
        for (int i = l; i <= r; i++)
            a[i] = r - l;

        func2(a, l + 1, r);
    }
}

void func(vector<int>& a, int l, int r) {
    int s = 0;
    for (int i = l; i <= r; i++)
        s += a[i];

    if (s <= (r - l + 1) * (r - l + 1)) {
        func2(a, l, r);
        op.push_back({l, r});
        for (int i = l; i <= r; i++) {
            a[i] = (r - l + 1);
        }
    } else {
        int mx = -1;
        int pos = -1;
        for (int i = l; i <= r; i++) {
            if (a[i] > mx) {
                mx = a[i];
                pos = i;
            }
        }

        if (pos != l)
            func(a, l, pos - 1);

        if (pos != r)
            func(a, pos + 1, r);
    }
}

int main() {
    int n;
    cin >> n;
    vector<int> a(n);
    for (int& i : a)
        cin >> i;

    func(a, 0, n - 1);
    int s = 0;
    for (int i : a)
        s += i;

    cout << s << " " << op.size() << "\n";

    for (auto [l, r] : op)
        cout << l + 1 << " " << r + 1 << "\n";
}