#include <iostream>
using namespace std;

const int MAX_N = 3e5 + 5;

struct node{
    int left, right;
    int sum;
};
node merge(node x, node y){
    return {x.left, y.right, x.sum + y.sum};
}

int n;
int nums[MAX_N];

int size_tree;
node tree[4 * MAX_N];

int place[MAX_N];

void update(int index, int change){
    index += size_tree - 1;
    tree[index].sum += change;
    index /= 2;
    while (index >= 1){
        tree[index] = merge(tree[2 * index], tree[2 * index + 1]);
        index /= 2;
    }
}

int position;

void find_pos(int index, int tree_node){
    int left_bound = tree[tree_node].left, right_bound = tree[tree_node].right;
    if (right_bound < index){
        return;
    }
    if (left_bound >= index and right_bound >= index){
        position += tree[tree_node].sum;
        return;
    }
    find_pos(index, 2 * tree_node);
    find_pos(index, 2 * tree_node + 1);
}

int main(){
    cin >> n;
    for (int i = 1;i <= n;i++){
        cin >> nums[i];
        place[nums[i]] = i;
    }
    int pos = n;
    int val = n;
    while (pos >= 1){
        while (pos >= 1 and nums[pos] != val){
            pos--;
        }
        if (pos >= 1){
            val--;
        }
    }
    cout << val << ' ' << val << '\n';
    size_tree = 1;
    while (size_tree < n){
        size_tree *= 2;
    }
    for (int i = 1;i <= size_tree;i++){
        tree[size_tree - 1 + i] = {i, i, 0};
    }
    for (int i = size_tree - 1;i >= 1;i--){
        tree[i] = merge(tree[2 * i], tree[2 * i + 1]);
    }
    for (int i = val;i >= 1;i--){
        position = 0;
        find_pos(place[i], 1);
        cout << position + place[i] << ' ' << 1 << '\n';
        update(position + place[i] - val + i, 1);
    }
    return 0;
}