#include <bits/stdc++.h>

struct Fenwick_Tree{
    std::vector<int> c;
    int n;
    Fenwick_Tree(int n) : n(n) {
        c.resize(n + 1);
    }
    void add(int x, int y) {
        for (int i = x; i <= n; i += i & -i) {
            c[i] += y;
        }
    }
    int query(int x) {
        int res = 0;
        for (int i = x; i > 0; i -= i & -i) {
            res += c[i];
        }
        return res;
    }

    int kth(int k) {
        int res = 0;
        for (int i = 1 << std::__lg(n); i > 0; i >>= 1) {
            if (res + i <= n && c[res + i] < k) {
                k -= c[res + i];
                res += i;
            }
        }
        return res + 1;
    }
};

using i64 = long long;

int main(){
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
    int n;
    std::cin >> n;
    std::vector<int> a(n + 1);
    std::vector<int> ord(n + 1);

    for (int i = 1; i <= n; i += 1){
        std::cin >> a[i];
        ord[i] = i;
    }
    std::sort(ord.begin() + 1, ord.end(), [&](int x, int y) {
        return a[x] > a[y];
    });
    int mn = n + 1;
    std::vector<std::pair<int, int> > go;
    for (int o = 1; o <= n; o += 1) {
        int i = ord[o];
        if (mn < i) {
            go.emplace_back(mn, i);
        }
        mn = std::min(mn, i);
    }
    std::sort(go.begin(), go.end(), [&](auto x, auto y) {
        if (x.first != y.first) return x.first > y.first;
        return a[x.second] > a[y.second];
    });
    Fenwick_Tree tree(n + 5);
    for (int i = 1; i <= n; i += 1){
        tree.add(i, 1);
    }
    i64 cost = 0;
    std::vector<std::pair<int, int> > res;
    for (auto [x, y] : go) {
        int p = tree.query(y);
        res.emplace_back(p, x);
        tree.add(y, -1);
        tree.add(x + 1, 1);
        cost += x;
    }
    std::cout << cost << " " << res.size() << "\n";
    for (auto [x, y] : res) {
        std::cout << x << " " << y << "\n";
    }
    return 0; 
}