#include <cstdio>

const int N = 300005;
int n, a[N], pos[N], b[N];

void add(int i, int d) {
	while (i <= n) {
		b[i] += d;
		i |= i + 1;
	}
}

int query(int i) {
	int s = 0;
	while (i >= 0) {
		s += b[i];
		i = (i & i + 1) - 1;
	}
	return s;
}

int main() {
	scanf("%d", &n);
	for (int i = 0; i < n; ++i) {
		scanf("%d", a + i);
		pos[a[i]] = i;
	}
	int l = n;
	while (l && a[l - 1] == l) --l;
	if (!l) printf("0 0\n");
	else {
		printf("%d %d\n", l - 1, l - 1);
		for (int i = l - 1; i >= 1; --i) {
			printf("%d %d\n", pos[i] + (l - 1 - i) - query(pos[i]) + 1, 1);
			add(pos[i] + 1, 1);
		}
	}
	return 0;
}